Chiarimenti sul quicksort

[Negative_creep]

Ciao a tutti, vorrei dei chiarimenti sul famoso algoritmo di quicksort. Da quanto ho capito dato un array A[n] di dimensione n, scelgo uno dei valori che sarà il mio PIVOT e utilizzo 2 indici "i" e "j" e attuo dei confronti/scambi di valori fino a trovare la posizione giusta per il mio pivot chiamando il metodo partition.

Ho provato l'algoritmo sulla frase A-S-O-R-T-I-N-G-E-X-A-M-P-L-E
e mentre sulle diverse lettere non ho avuto problemi, l'unica che non riesco a posizionare dall'inizio è la lettera "N" e qui mi sorge il dubbio sul fatto che non ho ben compreso l'algoritmo.

Vi scrivo il mio ragionamento. Scelgo N come pivot, inzio puntando i="A" e j="E", scorro la i e trovo "S" che è maggiore di N, mi fermo, guardo j, al momento punta ad E quindi attuo lo scambio fra S ed E ottenendo:

A-E-O-R-T-I-N-G-E-X-A-M-P-L-S

Ora i scorre di una posizione e trova subito la O, anche j decrementa e trova la L. Le scambio e mi trovo in questa situazione

A-E-L-R-T-I-N-G-E-X-A-M-P-O-S

Adesso scambio R con M ottendendo

A-E-L-M-T-I-N-G-E-X-A-R-P-O-S

In questo caso ora i punta a "T" e j punta a "A", scambio le due lettere con il seguente risultato A-E-L-M-A-I-N-G-E-X-T-R-P-O-S.

Ok, ora viene il problema, la i cerca una lettera > di "N" e la prima che trova è la "X", la j che puntava alla "T" decrementa di una posizione e si ritrova a puntare la "X" insieme il puntatore i.
i,j puntano a X quindi applico lo scambio mettendo la X in posizione di N e viceversa

A-E-L-M-A-I-X-G-E-N-T-R-P-O-S

La "N" in quella posizione non è corretta, e soprattutto prima del pivot N c'è la X che non fa parte di quella partition.
Il codice che ho tentato di utilizzare è il seguente


http://img231.imageshack.us/img231/5489/quicksort.th.jpg (http://img231.imageshack.us/i/quicksort.jpg/)

Sapete dirmi dove sbaglio? :help:

Grazie in anticipo..

[Negative_creep]

Nessuno? :rolleyes:

[wingman87]

Ciao a tutti, vorrei dei chiarimenti sul famoso algoritmo di quicksort. Da quanto ho capito dato un array A[n] di dimensione n, scelgo uno dei valori che sarà il mio PIVOT e utilizzo 2 indici "i" e "j" e attuo dei confronti/scambi di valori fino a trovare la posizione giusta per il mio pivot chiamando il metodo partition.

Ho provato l'algoritmo sulla frase A-S-O-R-T-I-N-G-E-X-A-M-P-L-E
e mentre sulle diverse lettere non ho avuto problemi, l'unica che non riesco a posizionare dall'inizio è la lettera "N" e qui mi sorge il dubbio sul fatto che non ho ben compreso l'algoritmo.

Vi scrivo il mio ragionamento. Scelgo N come pivot
Hai già sbagliato qui scegliendo N, almeno se segui l'algoritmo che hai postato, perché quell'algoritmo sceglie sempre l'ultimo elemento, cioè nel tuo caso E
, inzio puntando i="A" e j="E", scorro la i e trovo "S" che è maggiore di N, mi fermo, guardo j, al momento punta ad E
Ma E non viene considerato perché il confronto che effettui è:
less(v,a[--j])
il predecremento prima di effettuare il confronto fa sì che l'elemento puntato da j sia L che è > E, quindi si decrementa ancora fino ad arrivare ad A, a quel punto si ferma ed effettui lo scambio. Poi vai avanti seguendo l'algoritmo.

Questo applicando l'algoritmo che hai postato, se invece vuoi scegliere tu il pivot puoi applicare lo stesso algoritmo mettendo però prima il pivot che hai scelto in fondo (nella posizione r).
Come vedi il pivot in questo modo non si muove mai, solo alla fine, all'uscita del for, viene scambiato con l'elemento in posizione i che è appunto la posizione giusta del pivot.

[Negative_creep]

Azz...Grazie mille :sofico:
Praticamente l'algoritmo descritto dal libro fa la stessa cosa che dici tu giusto?
Sceglie sempre come pivot l'elemento in posizione R, che equivale a dire, scegli un pivot e mettilo in fondo, come hai suggerito tu, o sbaglio?


Comunque grazie veramente wingman87 per l'aiuto!!! ;)

[wingman87]

Azz...Grazie mille :sofico:
Praticamente l'algoritmo descritto dal libro fa la stessa cosa che dici tu giusto?
Sceglie sempre come pivot l'elemento in posizione R, che equivale a dire, scegli un pivot e mettilo in fondo, come hai suggerito tu, o sbaglio?
Esatto
Comunque grazie veramente wingman87 per l'aiuto!!! ;)
Di nulla, sono contento di essere stato d'aiuto ;)