Gli algoritmi di ordinamento ridispongono gli elementi di un array di n elementi di tipo T in modo crescente o decrescente, secondo una qualsiasi relazione d'ordine. Esistono svariati metodi di ordinamento, tra quelli più semplici vi sono i tre presentati nelle prossime sezioni.
E' comunque importante sapere che questi algoritmi non sono i migliori possibili, perchè usano un numero quadratico di operazioni. Esistono invece altri metodi, come il merge-sort o il quicksort (quest'ultimo però solo nel caso medio, anche se nella pratica è quello più usato), che necessitano di un numero dell'ordine di O(n log2n) operazioni.
Negli algoritmi che descriveremo T sarà ancora un tipo ordinabile, cioè che consente l'uso degli operatori di confronto <,<=,>,>=,!=, ==.
T sarà indicato genericamente con l'identificatore tipo, che potrà essere definito mediante un'opportuna typedef, ad esempio
typedef int tipo;
10.2.1 Algoritmo di ordinamento a bolle (Bubblesort)
L'ordinamento a bolle è molto semplice, ma non molto efficiente. Si basa sul seguente principio: se tra due elementi consecutivi, il primo è maggiore del secondo, allora questi due elementi sono sicuramente fuori posto e, come minimo, bisogna scambiarli fra di loro.
Questo controllo deve essere ripetuto più volte, infatti l'effetto di una singola passata che controlla ogni elemento con il precedente e in caso sfavorevole li scambia è solamente quello di garantire che l'elemento più grande sia messo al posto giusto, cioè all'ultimo posto dell'array.
Ad esempio partendo con l'array 3 4 7 9 11 8 5 2
una singola passata porta l'array alla seguente situazione 3 4 7 9 8 5 2 11
in cui solo 11 è al posto giusto.
Si noti che il confronto tra il penultimo e l'ultimo è inutile in quanto l'ultimo è il più grande. Nel nostro esempio si avrà
3 4 7 8 5 2 9 11
in cui anche 9 è adesso al posto giusto.
In generale occorreranno n-1 passate, ognuna delle quali controllerà sempre meno elementi, in quanto gli elementi messi al posto giusto da ogni passata precedente non vanno più spostati (né confrontati): int i,j; for(i=1;i<=n-1;i++) { for(j=0;j<n-i;j++) { if(a[j]>a[j+1]) { tipo temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }
Il numero di confronti è fisso e pari a (n-1)+(n-2)+...+1, che è quadratico in n. Il numero di scambi nel caso peggiore è anch'esso quadratico in n.
L'algoritmo può essere migliorato osservando che, se dopo un'intera passata, corrispondente ad un intero ciclo for interno, non si sono fatti scambi, allora l'array è già ordinato e si può uscire dal ciclo esterno (che diventa un ciclo do-while).
int i=1,j; bool scambia; do { scambia=false; for(j=0;j<n-i;j++) { if(a[j]>a[j+1]) { tipo temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; scambia=true; } } i++; }while(scambia);
10.2.2 Algoritmo di ordinamento per selezione
Questo secondo algoritmo di ordinamento si basa su questo semplice principio: l'elemento più piccolo in un array ordinato deve stare al primo posto, il secondo elemento più piccolo deve stare al secondo posto, e così via.
Perciò il procedimento è il seguente. Si trova l'elemento più piccolo dell'array e lo si scambia di posto con il primo elemento.
Poi si trova il secondo elemento più piccolo e lo si scambia con il secondo elemento dell'array. E' facile trovare il secondo elemento più piccolo, in quanto sarà l'elemento minore dell'array a partire dalla seconda posizione, dato che la prima adesso contiene già l'elemento complessivamente più piccolo.
Generalizzando si ottiene il seguente codice int i,j;
for(i=0;i<n-1;i++) {
// trova l'elemento più piccolo // a partire dall'elemento i-esimo int jmin=i;
for (j=i+1;j<n;j++) { if (a[j]<a[jmin]) { jmin=j; }
}
// dopo aver trovato il minimo corrente // lo scambio con l'elemento al posto i tipo temp=a[i];
a[i]=a[jmin]; a[jmin]=temp; }
Si noti che anche nel caso dell'ordinamento per selezione un volta che il penultimo elemento è stato messo al posto giusto, anche l'ultimo elemento sarà stato sistemato, e quindi il ciclo for più esterno può terminare dopo n-1 passi.
Ad esempio partendo da 3 4 7 9 8 5 2 11 si ottiene al primo passo
2 4 7 9 8 5 3 11
e al secondo passo 2 3 7 9 8 5 4 11
E' uno degli algoritmi più efficienti, perché fa solo n-1 scambi. Purtroppo anche questo algoritmo ha bisogno di un numero quadratico di confronti.
10.2.3 Algoritmo di ordinamento per inserzione
Un ulteriore algoritmo di ordinamento è quello per inserzione. Si tratta di un algoritmo basato sul metodo che usa un giocatore di carte (ad esempio a scala quaranta, ramino, ecc.) per ordinare le carte che ha in mano. Il procedimento si basa sullo spostamento delle carte in modo da creare una zona già ordinata che parte dalla mano sinistra: ogni carta della zona non ordinata è inserita nel posto che le compete all'interno della zona già ordinata.
Ad esempio avendo già disposto in ordine un asso di cuori, un tre di picche, un cinque ed un sei di fiori, il posto per un quattro di quadri è fra il tre ed il cinque. Ogni volta che si inserisce una carta in mezzo alle altre, avviene uno scorrimento delle carte di cui il giocatore non si rende conto (fondamentalmente perché le carte scivolano facilmente).
Per trasformare questo procedimento in un algoritmo funzionante su un array bisogna proprio esplicitare l'idea di far scorrere gli elementi dell'array per far posto all'elemento da inserire.
int i,j;
for(j=1;j<n;j++) { tipo temp=a[j];
// sistemare a[j] nella parte a[0..j-1] già ordinata i=j-1;
while(i>=0 && a[i]>temp) { a[i+1]=a[i];
i--; }
a[i+1]=temp; }
Si notino alcune caratteristiche dell'algoritmo. Innanzitutto il primo elemento non viene inizialmente toccato: la parte già ordinata alla partenza è proprio costituita dal solo primo elemento.
L'algoritmo poi sistema tutti gli altri elementi nella parte già ordinata dell'array. L'elemento da sistemare è memorizzato nella variabile temp e l'algoritmo cerca il punto corretto in cui l'elemento da sistemare deve essere inserito nella parte già ordinata dell'array.
Quindi inizia un ciclo che scandisce la parte già ordinata iniziando dal fondo e che si ferma quando trova un elemento minore o uguale a quello da inserire, ogni volta ricopiando l'elemento controllato di una posizione verso destra, in modo da creare lo spazio dell'inserimento. Ad esempio partendo dall'array
3 4 7 9 8 5 2 11
con i=4, si deve inserire 8 tra 7 e 9, ottenendo 3 4 7 8 9 5 2 11
La ricerca termina anche quando tutto l'array è stato scandito, cioè quando l'elemento da inserire è minore di tutti gli elementi della parte già ordinata.
Anche tale algoritmo ha un costo quadratico in n sia in termini di confronti che di assegnamenti.
10.3 Esercizi
10.1. Adattare la ricerca binaria al caso di array ordinati in senso decrescente
10.2. Adattare un algoritmo di ordinamento al caso di array di strutture, ordinati in base ad un campo, ad esempio ordinare un array di persona in base all'età
10.3. Adattare un algoritmo di ordinamento al caso in cui gli elementi da ordinare sono squadre nazionali olimpiche, cioè strutture con i campi nome della nazione, numeri di medaglie d'oro, medaglie d'argento e medaglie di bronzo. La relazione d'ordine tra squadre è di preferire quelle con più ori, a parità, più argenti e ulteriore parità più bronzi.