Newsgroup: it.scienza.informatica
Titolo: Algoritmo Quick sort

Qualcuno può spiegarmi il funzionamento dell'algoritmo quick sort per
l'ordinamento di un vettore?
    Grazie
            Ciao

 ha scritto nel messaggio
news:cotS7.304629$sq5.14...@news.infostrada.it...


 wrote in message
news:cotS7.304629$sq5.14...@news.infostrada.it...

E' un algoritmo ricorsivo. Partendo dal vettore completo si sceglie un
elemento che chiameremo Pivot. Come sceglierlo lo vediamo dopo. Il Pivot
avrà un valore fra quelli presenti nel vettore. A questo punto ci si
propone di suddividere il vettore in due sottovettori. Visualizzando il
vettore orizzontalmente e supponendo che il primo elemento sia a
sinistra e di volre ordinare in ordine crescente, vogliamo che che tutti
gli elementi con indice compeso nell'intervallo [0,p] siano minori o
uguali all'elemento pivot e che tutti gli elementi con indice compreso
nell'intervallo ]p,N[ dove N è il numero di elementi del vettore (ovvero
l'intero vettore ha indice compreso in [0,N[) siano maggiori o uguali al
pivot.
A questo punto si ripete l'algoritmo ricorsivamente sui due sottovettori
così trovati.
La sezione centrale dell'algoritmo, supponendo che la variabile "pivot"
abbia lo stesso valore dell'elemento pivot e che il vettore (che
potrebbe essere solo un sottovettore) sia rappresentato da V e inizi
dall'elemnto "first" e abbia dimensione "len" e che siano disponibili
due variabili indice "i" e "j" e una variabile temporanea "temp" dello
stesso tipo degli elementi del vettore, potrebbe essere:
i=first;
j=first+len-1;
while ( i<=j; ) {
    while ( i<=j && V[i]<=pivot )
        ++i;
    while ( i<=j && V[j]>=pivot )
        --j;
    if ( i<j ) {
        t=V[i];
        V[i]=V[j];
        V[j]=t;
        ++i;
        --j;
    }
}
Gli indici i e j percorrono, in direzioni opposte, i due sottovettori.
Il primo while sposta in avanti l'indice i che inizia dal primo elemento
fino a trovare un elemento maggiore del pivot (e pertanto che non deve
stare nel primo sottovettore).
Il secondo while fa la stessa cosa all'indietro sull'altro sottovettore
usando j.
Ovviamente i due indici non si devono incrociare.
Quando entrambe gli indici si sono fermati, se ancora non si sono
incrociati (scopo dell'if), scambiamo i due elementi. L'elemento iesimo
si trova nel primo sottovettore ma dovrebbe stare nel secondo, quello
jesimo si trova nel secondo ma dovrebbe stare nel primo. Scambiandoli
ciascuno di essi si troverà nel corretto sottovettore e i due indici
possono quindi essere incrementati (in logica negativa l'indice j viene
ovviamente decrementato).
A questo punto se gli indici ancora non si sono scambiati continuamo la
ricerca con i due while.
All'uscita dal while esterno avremo che:
se j<=first il primo sottovettore è vuoto
altrimenti [first,j] contiene solo elementi minori o uguali al pivot
se i>=first+len-1 il secondo sottovettore è vuoto
altrimenti [i,first+len-1] contiene solo elementi maggiori o uguali al
pivot
sicuramente i=j+1
Quindi j corrisponde all'indice p indicato all'inizio nella parte
teorica.
L'algoritmo prosegue ricorsivamente ordinando i due sottovettori.
Si possono notare due cose. La prima è che quando il vettore è molto
corto l'algoritmo non è efficiente. Ordinare con questo algortitmo
vettori di un solo elemento non è efficiente. Ordinare vettori di due
elementi è più efficiente farlo con:
if ( v[0]>v[1] ) {
    t=V[0];
    V[0]=V[1];
    V[1]=t;
}
Domanda: quale è il limite?
Risposta: per vettori (o sottovettori) di lunghezza inferiore a circa
10-12 elementi è più efficiente usare un insertion-sort.
Pertanto prima di applicare il quick-sort conviene verificare che il
vettore (ovvero il sottovettore) sia lungo almeno una decina di elementi
e in caso contrario il quicksort richiama un insertion-sort.
La seconda cosa da notare è che la scelta del valore pivot influisce
sulle prestazioni. Idealmente il valore pivot dovrebbe essere sempre
quello "mediano" fra tutti i valori. In realtà calcolare il valore
mediano costa troppo. La tecnica più usata è quella del "median of 3".
Ovvero si prende il valore mediano fra il primo, l'ultimo e quello
centrale del vettore non ordinato.
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

             Ciao
Ciao
Diego

 ha scritto nel messaggio
news:cotS7.304629$sq5.14...@news.infostrada.it...
