next up previous contents index
Next: Enumerati Up: Ordinare un array Previous: Funzioni ricorsive   Indice   Indice analitico

Quick sort

Il metodo che stiamo per presentare è detto quick sort, che significa in italiano ``ordinamento veloce''; in realtà non si tratta di presunzione: tale algoritmo è uno dei più veloci oggi conosciuti. Tuttavia non è particolamente intricato: ad un primo sguardo si tratta semplicemente di Un algoritmo che effettua le seguenti operazioni è il seguente:

void quicksort (int v[], int inf, int sup) {
  int s = inf;
  int d = sup;
  int perno = v[(inf + sup) / 2];
  do {
    while (v[s] < perno)
      s++;
    while (v[d] > perno)
      d--;
    if (s <= d) {
      scambia (v[s], v[d]);
      s++;
      d--;
    }
  } while (s <= d);
  if (inf < d)
    quicksort (v, inf, d);
  if (s < sup)
    quicksort (v, s, sup);
}
Grazie a questo algoritmo, l'ordinamento di un gran numero di dati è sensibilmente piè veloce; tuttavia esso non è indicato per strutture dati ad accesso sequenziale, di cui vedremo in seguito alcuni esempi. Comunque lo studio delle possibili tecniche di ordinamento sarebbe, all'interno di questo corso, quantomeno pesante; per cui si è preferito dare non più di qualche cenno sull'argomento. Nel caso (remoto) si avesse la necessita di algoritmi di ordinamento davvero efficienti, si faccia ricorso alle librerie fornite a corredo del C++, oppure ad altre scritte da terze parti; non si faticherà molto a trovarne un gran numero, anche sotto licenze di tipo ``free''.

Vediamo ora se tale algoritmo funziona. La dimostrazione rigorosa ha una utilità fine a se stessa, per cui preferiamo prendere un array di esempio e verificare che in tale caso specifico l'algoritmo è in grado di ordinarlo. Prendiamo

0 1 2 3 4 5 6
6 4 3 2 7 1 5
inf=0, sup=6
ove la prima riga indica corrisponde agli indici degli elementi dell'array e la seconda il contenuto dello stesso; inizialmente perno corrisponde al quarto elemento dell'array (2), per cui bisogna fare in modo che tutti gli elementi a sinistra di $2$ siano minori di esso e tutti quelli a destra siano maggiori; dopo alcuni cicli (due) si avrà dunque:
0 1 2 3 4 5 6
1 2 3 4 7 6 5
inf=0, sup=6, s=2, d=1
siccome è inf<s e s<sup dobbiamo effettuare due chiamate a quicksort:
chiamata 2)
abbiamo:
0 1
1 2
inf=0, sup=1
che, si provi a verificare per esercizio, termina lasciando inalterato il vettore;
chiamata 3)
abbiamo:
0 1 2 3 4
3 4 7 6 5
inf=0, sup=4
ove il perno è il terzo elemento dell'array (7); dopo due cicli otteniamo la seguente configurazione:
0 1 2 3 4
3 4 5 6 7
inf=0, sup=4, s=4, d=3
la quale porta solo una chiamata, essendo vero che inf<d ma non che s<sup; tale chiamata avviene sul seguente array:
0 1 2 3
3 4 5 6
che non porta nuove chiamate.
A questo punto si ha la richiusura delle chiamate aperte e, quasi magicamente, il nostro array è:
0 1 2 3 4 5 6
1 2 3 4 5 6 7

ex-2
si scriva un programma che ordini cinque numeri immessi dall'utente; si utilizzi il metodo selection sort;
ex-3
si modifichi la funzione selectionSort in maniera tale che restituisca il vettore ordinato in verso decrescente;
ex-4
si scriva una funzione che accetti un array e il numero dei suo elementi, e ordini in verso crescente i numeri pari e in verso decrescente i numeri dispati, utilizzando il metodo selection sort;
ex-5
si scriva un programma che stampi i primi $n$ termini della successione di Fibonacci; si utilizzi un algoritmo ricorsivo;
ex-6
si scriva una funzione ricorsiva che moltiplichi tra di loro due numeri interi;
ex-7
si scriva una funzione ricorsiva che ritorni il valore booleano true se il suo argomento è pari, false se dispari;
ex-8
si eseguano gli esercizi 1, 2, 3 applicando il metodo quick sort.


next up previous contents index
Next: Enumerati Up: Ordinare un array Previous: Funzioni ricorsive   Indice   Indice analitico
Claudio Cicconetti
2000-09-06