[C] Help quicksort

[Solido]

Raga non riesco a capire quest'algoritmo:mc:
da quello che ho capito io, dato un vettore si sceglie un elemento pivot e in base a questo si opera l'ordinamento nei sottovettori creati dal pivot, prima si guarda nel sottovett di sinistra e se gli elementi sono minori del pivot si scorre +1 in avanti mentre se sono maggiori si scambia e si mette a destra, mentre per l'altro semivett si procede al contrario.


Mentre nel libro trovo scritto che dopo aver esaminato i semivett se l'indice della parte inf del blocco è <= all'indice dell'elem della parte superiore allora effettuo lo scambio tra i rispettivi vettori!
non capisco come mai <= e non >=


questo è un esempio dell'algoritmo che ho trovato in rete:


void sort(int array[], int begin, int end) {
int pivot, l, r;
if (end > begin) {
pivot = array[begin];
l = begin + 1;
r = end+1;
while(l < r)
if (array[l] < pivot)
l++;
else {
r--;
swap(array[l], array[r]);
}
l--;
swap(array[begin], array[l]);
sort(array, begin, l);
sort(array, r, end);
}
}



:help: :help: :help:

[Doriän]

Un'idea senza guardare troppo l'algoritmo...può darsi che sia per ordinare in ordine decrescente piuttosto che crescente?

[Solido]

Si fino a li ci sono :D

[eliano]

Esistono varie implementazioni del quicksort, ognuna ottimizzata per un caso particolare, quindi, a mio parere, dovresti controllare innanzitutto che la versione che hai riportato nel tuo post (che credo sia tratta da una pagina di wikipedia) sia identica a quella del tuo testo.
Guardando il codice che hai postato, e se ho capito bene la domanda, la spiegazione è nel funzionamento base dell'algoritmo: per poter effettuare lo scambio hai bisogno di avere contemporaneamente un elemento maggiore ed uno minore del pivot da scambiare tra loro.
La questione fondamentale è che l'algoritmo di base si preoccupa di creare due semivettori che contengano, rispettivamente, gli elementi maggiori e minori del pivot; nel codice postato viene scelto come pivot il primo elemento dell'array e il vettore viene diviso in due classi di elementi rispetto ad esso. Alla fine l'elemento pivot viene inserito nel giusto semivettore (fai attenzione alle condizioni di incremento di l e decremento di r) e si procede ricorsivamente sui due semivettori.
Sarebbe utile che tu facessi un pò di prove con carta e penna per capire il meccanismo di funzionamento dell'algoritmo: in particolare dovresti controllare alcuni casi limite appositamente costruiti.

[Solido]

Si è vero quello del mio testo è diverso... è solo che non capivo bene i passaggi... lo scopo dell'algoritmo lo so, quello ch mi traeva in inganno è quella che avevo postato sopra:

Mentre nel libro trovo scritto che dopo aver esaminato i semivett se l'indice della parte inf del blocco è <= all'indice dell'elem della parte superiore allora effettuo lo scambio tra i rispettivi vettori!
non capisco come mai <= e non >=

[Furla]

stiamo parlando di indici, è ovvio che se l'indice di sinistra è maggiore dell'indice di destra non effettui lo scambio perché si sono incontrati e i due sottoarray sono pronti alle due chiamate ricorsive; anche nella versione da te postata la condizione per procedere è è sinistra < destra.

[Solido]

stiamo parlando di indici, è ovvio che se l'indice di sinistra è maggiore dell'indice di destra non effettui lo scambio perché si sono incontrati e i due sottoarray sono pronti alle due chiamate ricorsive; anche nella versione da te postata la condizione per procedere è è sinistra < destra.





Infatti SINISTRA < DESTRA e nn viceversa e poi dice: 'indice della parte inf del blocco è <= all'indice dell'elem della parte superiore allora effettuo lo scambio tra i rispettivi vettori!... nn dovrebbe essere >=???
da quello che avevo capito io DEVE essere minore uguale:stordita: