[java] quicksort

[noodles83]

ciao!

sto cercando di implementare il quick sort sia la versione normale che quella randomizzata.

La prima mi viene senza problemi, la senconda invece non mi da i risultati che volevo e non caspisco il perchè... mi date un consiglio?

private static int randomPartition(int[] array,int start, int end){
int index = (int)Math.random() * end;
scambio(array,start,index);

return partition(array,start,end);
}

private static int partition(int[] array,int start, int end){
int pivot = array[start];
int i = start - 1;
int j = end + 1;
while (true) {
while (true) {
j--;
while (array[j] > pivot)
j--;
i++;
while (array[i] < pivot)
i++;
if (i < j)
scambio(array, i, j);
else
return j;
}
}
}

public static void quicksort(int[] array, int start, int end){
if(start < end){
int pivot=randomPartition(array,start,end);
quicksort(array,start,pivot);
quicksort(array,pivot+1,end);
}
}

dove sbaglio?

[noodles83]

up

[Andrea16v]

Che errore ti dà?

[noodles83]

nessun errore in compilazione...semplicemente non ordina...

[noodles83]

se non uso il pivot preso random però funziona... non capisco il prechè.

[Barbalbero]

A prima vista direi che


private static int randomPartition(int[] array,int start, int end){
int index = (int)Math.random() * end;
scambio(array,start,index);

return partition(array,start,end);
}


quando calcoli index, secondo me, devi moltiplicare non per end, ma per (end-start)

[Barbalbero]

...e di conseguenza fare

scambia(array,start,start+index);

Prova così

[noodles83]

no nulla... sempre il solito problema! :muro:

[noodles83]

no no ferma i lavori!! ora va!! :D avevi ragione te! grazie mille!

ma mi potresti spiegare se puoi il perchè... :rolleyes:

[Barbalbero]

Questo è l'array che devi ordinare:

OOOOOOOOOOOOOOOOOOOOOOO

Tu scegli un pivot random e controlli solo una parte(OOOO) del vettore ricorsivamente:

OOOOOOOOOOOOOOXXXXXXXXXX

Poi rifai la stessa cosa ancora e ancora.
Arriverai ad esempio a dover considerare il seguente array(OOO):

XXXXXOOOOOOOOOXXXXXXXXXXX

A questo punto START indicherà l'inizio dell'array OOO ed END ne indicherà la fine.
Se tu generi un numero random da 0 ad END andrai a controllare anche una parte di array che non ti interessa (le XXX a sinistra)
Allora devi generare un numero minore di END-START e sommarlo a START.
In tal modo controlli solamente l'array di OOO.