oridnamento quicksort

[starmar]

Ho letto moltissime guide in rete, ma non mi è ancora chiarissimo questo tipo di ordinamento, che diciamocelo , non è tra i + immediati:
Qualche anima pia che mi da una manina?? grazie a tutti.

P.s. solo teoria il codice non è un problema ;)

[stdecden]

Per cominciare quicksort é un algoritmo ricorsivo che funziona così:

scegli un elemento (pivot) e sposta tutti gli elementi piú piccoli di questo sulla sinistra, e quelli piú grandi sulla destra:

[4]765321 // il 4 è il "Pivot"
321[4]765

Ora ripeti l' algoritmo per tutti gli elementi precedenti al pivot, e poi a quelli successivi:

[3]21... // Numeri prima del pivot
21[3]...
...[7]65 // Numeri dopo il pivot
...65[7]

Ancora un'altro passo:

[2]1...
1[2]...

...6[5]
...[5]6

e infine avrai una lista ordinata:

1[2][3][4][5]6[7]

se ci sono problemi chiedi

[starmar]

Grazie ma per il discorso degli indici i e j?? Quando si scambiano? Scusa ma al prof dovrò sicuramente spiegarlo tramite indici ;)

[wingman87]

Dipende da quale versione del quicksort vi ha spiegato. Se si tratta di quello illustrato da stdecden l'algoritmo utilizzato è il seguente:
Durante una generica chiamata ricorsiva stai esaminando una porzione di array delimitata dagli indici inf e sup compresi.
Se questa porzione è vuota terminiamo, altrimenti...
L'elemento di indice inf è il pivot per questa chiamata.
http://img14.imageshack.us/img14/4080/quick01.jpg

Ora utilizziamo un algoritmo che dato un valore k e una porzione di array sposti sulla sinistra tutti gli elementi <= k e a destra gli elementi > k e lo utilizziamo sulla porzione di array da inf+1 a sup e con k=pivot.
http://img512.imageshack.us/img512/5756/quick02.jpg

Al generico passo di questo algoritmo ci troveremo in questa situazione: sulla sinistra abbiamo una porzione di array già esaminata in cui ogni elemento è <=k, al centro una porzione da esaminare e a destra una porzione già esaminata (vediamo tra poco come) in cui ogni elemento è >k
http://img512.imageshack.us/img512/355/quick03.jpg

Con gli indici i e j indichiamo rispettivamente il prossimo e l'ultimo elemento da esaminare. Quindi, se il valore puntato da i è <=k incremento i, altrimenti scambio il valore puntato da i con quello puntato da j e decremento j.
Il ciclo termina quando non ci sono più elementi da esaminare, cioè quando la porzione di array delimitata da i e j è vuota, ossia quando i=j+1 (i ha superato j).
A questo punto spostiamo il pivot nel mezzo, scambiandolo con l'elemento di indice j (infatti al termine dell'algoritmo di ripartizione questo punta sicuramente all'ultimo elemento <=k, al più punta al pivot stesso).
Infine richiamiamo il quicksort sulla porzione a sinistra del pivot e su quella alla sua destra.