Next: Enumerati
Up: Ordinare un array
Previous: Funzioni ricorsive
  Indice
  Indice analitico
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
- scegliere un elemento perno dell'array, magari l'elemento in posizione centrale;
- fare in modo che tutti gli elementi a sinistra del perno siano minori di esso e quelli a destra maggiori;
- applicare l'algoritmo quick sort ricorsivamente alle due metà risultati.
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
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:
che, si provi a verificare per esercizio, termina lasciando inalterato il vettore;
- chiamata 3)
- abbiamo:
ove il
perno
è il terzo elemento dell'array (7
); dopo due cicli otteniamo la seguente configurazione:
la quale porta solo una chiamata, essendo vero che inf<d
ma non che s<sup
; tale chiamata avviene sul seguente array:
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
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: Enumerati
Up: Ordinare un array
Previous: Funzioni ricorsive
  Indice
  Indice analitico
Claudio Cicconetti
2000-09-06