Vorrei una spiegazione dettagliata sul funzionamento dell’algoritmo quicksort per l’ordinamento di una lista di numeri. Grazie.

In molti problemi reali si sente l’esigenza di ordinare dati. Si pensi
all’elenco telefonico o al dizionario della lingua italiana; sarebbe molto
complicato ricercare un abbonato al servizio telefonico o un vocabolo nel
dizionario se i dati (abbonati o vocaboli) fossero memorizzati alla rinfusa
senza seguire un ordine logico. È ovvio che sia l’elenco telefonico sia
il vocabolario devono essere ordinati in ordine alfabetico, affinché sia
possibile ricercare velocemente ciò che ci interessa.

L’informatica viene in aiuto per risolvere il problema dell’ordinamento
in modo automatico mediante l’esecuzione di algoritmi chiamati di ordinamento.

Il Quicksort rientra nella classe degli algoritmi di ordinamento “general
purpose” (uso generale).

Analizziamo l’idea di base.

Per semplificare l’esposizione dell’algoritmo si preferisce utilizzare
vettori di numeri.

Dato un vettore v di numeri:

10

23

12

1

6

75

34

21

49

9

si vuole ordinare in modo decrescente mediante l’algoritmo quicksort
ottenendo il seguente vettore:

75

49

34

23

21

12

10

9

6

1

Idea di base di quicksort

  1. scegli l’elemento centrale del vettore (detto pivot) e memorizzalo
    in una variabile k
  2. metti a sinistra gli elementi >= pivot
  3. metti a destra gli elementi < pivot
  4. ordina ricorsivamente la parte destra e la parte sinistra.

1. Si sceglie un elemento (detto pivot) nel nostro esempio 6 (k=6).


10

23

12

1

6

75

34

21

49

9

2. metti a sinistra gli elementi <= pivot

3. metti a destra gli elementi >= pivot

10

23

12

9

49

75

34

21

6

1

Applicare l’algoritmo ricorsivamente sia per la parte sinistra sia
per la parte destra.

La parte più difficile dell’algoritmo è dividere il vettore v
in due sottoinsiemi (destro e sinistro) rispetto al pivot scelto.

La procedura per dividere in due parti il vettore si chiama “partition”.

Idea di base di partition

Facciamo crescere contemporaneamente la regione con gli elementi >=
pivot sulla sinistra e la regione con gli elementi <= pivot sulla destra.


Siano i e i due contatori che memorizzano un indice del vettore v.

Sia k l’elemento posizionato al centro di v.

Porre i uguale al limite inferiore del vettore, i uguale al limite
superiore (nel nostro esempio i = 1 e i = 10).

Ripetere

Incrementare i sino a che v[i] è minore o uguale di k.

Decrementare i sino a che v[j] è maggiore o uguale
di k.

Scambiare v[i] con v[j].

Sino a che i è minore di j.

Esempio:

Incrementiamo i fino a quando v[i] < = K e decrementiamo
j fino a quando v[j] >= K

10

23

12

1

6

75

34

21

49

9

I = 1

 

 

 

K = 6

 

 

 

 

J = 10

 

I = 2

 

 

 

 

 

 

 

 

 

 

I = 3

 

 

 

 

 

 

 

 

 

 

I = 4

 

 

 

 

 

 

 


Scambiamo v[i] con v[j].

10

23

12

1

6

75

34

21

49

9

 

 

 

9

 

 

 

 

 

1

ottenendo il vettore:

10

23

12

9

6

75

34

21

49

1

ripetiamo fin quando i < j

10

23

12

9

6

75

34

21

49

1

 

 

 

I = 4

K = 6

 

 

 

 

J = 10

 

 

 

 

I = 5

 

 

 

J = 9

 

Scambiamo v[i] con v[j].

10

23

12

9

6

75

34

21

49

1

 

 

 

 

49

 

 

 

6

 


ottenendo il vettore:

10

23

12

9

49

75

34

21

6

1

essendo a questo punto i < j dobbiamo continuare con il “partition”
ottenendo il vettore partizionato

 

10

23

12

9

49

75

34

21

6

1

Arrivati a questo punto bisogna applicare nuovamente l’algoritmo Quicksort
al vettore ottenuto.

Si osservi che per semplicità di esposizione si è scelto come pivot
sempre l’elemento centrale del vettore di numeri.

È stato dimostrato che una scelta inopportuna del pivot porta ad una
complessità di tempo dell’ordine di n2, inaccettabile in problemi
in cui la dimensione n del vettore è molto grande.

È possibile dimostrare matematicamente che, scegliendo casualmente
il pivot, il tempo di esecuzione del Quicksort è proporzionale a
n log n molto inferiore a n2.