Supponiamo di avere un vettore, ad es. di numeri interi, e di volerlo ordinare in ordine crescente, cioè dall'elemento più piccolo al più grande. Questo significa che, se per esempio il contenuto iniziale del vettore è:
dopo l'ordinamento il nuovo contenuto sarà:
Vi sono molti metodi per ordinare un vettore (per una rassegna un po' più completa si rimanda il lettore a Wikibooks). Due fra gli algoritmi più semplici sono:
- Selection Sort
- Bubble Sort
L'idea è la seguente: si trova l'elemento minimo (quello col valore più piccolo di tutti) e lo si sposta nell'elemento zero (il primo elemento) del vettore, scambiandolo di posto con quest'ultimo:
A questo punto l'elemento zero è sistemato (contiene già il valore più piccolo). Si procede quindi a una nuova ricerca del minimo sugli elementi restanti (dall'1 alla fine del vettore). Analogamente a quanto fatto prima, il nuovo minimo viene scambiato di posto con l'elemento di posizione 1 (il secondo del vettore):
Il procedimento prosegue allo stesso modo fino alla fine del vettore.
Per implementare l'algoritmo occorrono due cicli annidati (uno dentro l'altro) così (n rappresenta il numero di elementi del vettore):
for(i=0; i<n-1; i++)
{
min = i;
for(j=i+1; j<n; j++)
if(vet[j] < vet[min])
//cambiare questa condizione per invertire l'ordine
min = j;
temp=vet[min];
vet[min]=vet[i];
vet[i]=temp;
}
Si noti che il ciclo interno inizia da i+1 (cioè dall'elemento successivo all'ultimo elemento ordinato) e si limita a memorizzare la posizione dell'elemento minimo. Lo scambio viene fatto solo una volta che questa posizione è stata individuata (nel ciclo esterno).
Il tempo di esecuzione di questo algoritmo cresce ovviamente al crescere delle dimensioni del vettore da ordinare.
Cambiando la diseguaglianza indicata nel codice, l'ordinamento può essere facilmente invertito (dal più grande al più piccolo, decrescente).
Con questo secondo metodo, si confrontano gli elementi del vettore a due a due, partendo dall'ultimo (anzi, dal penultimo). Se si trovano due elementi in ordine "scorretto", essi vengono scambiati di posto. Per esempio nel nostro caso, la prima esecuzione del ciclo produrrà gli scambi seguenti:
Si osservi come, al termine della prima scansione, l'elemento più piccolo del vettore sia stato spostato in posizione zero.
for (j = 0; j < n; j++ )
{
for (i=n-1; i>=j; i--)
{
if (vet[i]>vet[i+1]) //cambiare questa condizione per invertire l'ordine
{
tmp = vet[i];
vet[i] = vet[i+1];
vet[i+1] = tmp;
}
}
}
Questo algoritmo non è molto efficiente e i suoi tempi di calcolo crescono al crescere delle dimensioni del vettore. Tuttavia vi sono diverse varianti di questo algoritmo che consentono di migliorarne le prestazioni. Per esempio, nel caso di vettori già parzialmente ordinati, è possibile aumentare la velocità dell'algoritmo fermandolo quando non ci sono più scambi (quando questa condizione si verifica, il vettore è ovviamente ordinato).
Sito realizzato in base al template offerto da
http://www.graphixmania.it
