Salve,
ringrazio anticipatamente chi mi da una mano a risolvere questo problema...
realizzare un algoritmo di ordinamento in Java che restituisce anche gli indici di posizione..
con un esempio tutto sarà più chiaro
Se ho A = [3 1 1 2 0]
A ordinato = [0 1 1 2 3]
gli indici sono [4 1 2 3 0]
quindi è un ordinamento degli indici...
grazie mille
Ti interessano le prestazioni dell'algoritmo?
Con un selection sort è facile: basta che quando trovi l'elemento minimo nell'array da ordinare, prima di metterlo al suo posto ti segni il suo indice.
Se devi segnarti gli indici su un quicksort o un mergesort la cosa è più interessante... Ma non puoi banalmente confrontare l'array ordinato con l'array da ordinare? In questo caso però peggiori le prestazioni a O(n^2) e allora tanto vale usare il selection sort...
Aspetta puoi anche fare così: per ogni elemento da ordinare crei un oggetto "coppia" formata dall'elemento stesso e dal suo indice e inserisci queste coppie in un array (in O(n)). Poi ordini l'array con quicksort ed infine scorri l'array ordinato estraendo da ogni coppia il suo indice!
In questo modo mantieni le prestazioni di quicksort.
Ho provato...
i problemi nascono quando ci sono valori di ugual valore... cioè che si ripetono più volte
Credi un vettore di boolean di appoggio. Se un elemento lo hai già dichiarato "ordinato", metti true o false (dipende da come vuoi ragionare), altrimenti lo processi e poi metti il flag nel vettore.Originariamente inviato da robs05
Ho provato...
i problemi nascono quando ci sono valori di ugual valore... cioè che si ripetono più volte
Hai provato con quale tipo di ordinamento? Non mi viene in mente come i duplicati possano creare problemi, anche nel caso più semplice di selection sort...Originariamente inviato da robs05
Ho provato...
i problemi nascono quando ci sono valori di ugual valore... cioè che si ripetono più volte
Permessi di invio
Rispondi quotando