Impara a Programmare, Lezione 2: Algoritmi di ordinamento: Insertion Sort e Counting Sort

Algoritmi di ordinamento: Insertion Sort e Counting Sort

In molte applicazioni che richiedono un algoritmo di ordinamento e` sufficiente implementare un algoritmo elementare. Di norma, i programi di ordinamento sono utilizzati una sola volta, o al piu` poche volte. Se il numero di elementi da ordinare non e` troppo grande (ad esempio, minore di cinquecento) puo` essere piu` conveniente seguire un metodo semplice che implementarne e verificarne uno piu` sofisticato.
Praticamente tutti i metodi elementari analizzati ordinano un file di N elementi disposti in modo casuale in N² passi. Se N e` sufficientemente piccolo questo puo` non rappresentare un problema, ed inoltre, se gli elementi non sono in ordine casuale, alcuni di questi procedimenti possono essere molto piu` veloci di quelli piu` complessi.

Insertion Sort

Un algoritmo semplice e didattico, per comprendere il problema dell’ordinamento, e` l’ordinamento per inserzione. Questo e` il metodo usato di solito dai giocatori per ordinare in mano le carte: cioe` considerando un elemento alla volta, inserire ciascun elemento al proprio posto tra quelli gia` considerati. L’elemento considerato viene inserito nel posto rimasto vacante in seguito allo spostamento di un posto a destra degli elementi piu` grandi, come mostrato in figura 1:

La S in seconda posizione e` maggiore della prima A, per cui non deve essere spostata. Quando si incontra la O in terza posizione, questa viene scambiata con la S disponendo le lettere A O S in ordine, etc. Questo procedimento e` realizzato dal programma che segue. Per ogni i tra 2 ed N, gli elementi a[1],…,a[i] sono ordinati inserendo a[i] nella giusta posizione tra gli elementi ordinati a[1],…,a[i-1]:

Il Bubble Sort

Un metodo elementare di ordinamento comunemente insegnato nei corsi introduttivi e` il Bubble Sort. Il procedimento consiste nell’attraversare il file, scambiando se necessario gli elementi adiacenti, fino a quando non e` piu` richiesto alcuno scambio e il file risulta ordinato.

Un implementazione di questo metodo viene illustrata di seguito:

bubble(int a[], int N) {
int i,j,t;
for(i=N;i>=1;i--){
		for(j=2;j<=I;j++){
			if(a[j-1]>a[j]){
				t=a[j-1];
				a[j-1]=a[j];
				a[j]=t;
			}
		}
}
}

E` necessario un attimo di riflessione per convincersi che questo metodo funziona. A questo scopo, basta notare che ogni qualvolta si incontra l’elemento piu` grande durante la prima passata, questo viene scambiato con qualsiasi altro elemento si trovi alla sua destra fino a quando non raggiunge la posizione di estrema destra dell’array. Quindi, durante la seconda passata, il secondo elemento piu` grande viene spinto nella penultima posizione, etc.

Counting Sort

Una situazione molto speciale, per la quale esiste un semplice algoritmo di ordinamento, e` la seguente: “ordinare un file di N record le cui chiavi sono interi distinti compresi tra 1 ed M”:

for(j=0;j<M;j++)
  count[j]=0;
for(i=1;i<=N;i++)
  count[a[i]]++;
for(j=1;j<M;j++)
  count[j]=count[j-1]+count[j];
for(i=N;i>=1;i--)
  b[count[a[i]]--]=a[i];
for(i=1;i<=N;i++)
  a[i]=b[i];

L’idea è quella di contare il numero di chiavi presenti per ciascun valore, ed usare questa grandezza per spostare i record nella loro posizione finale durante una seconda passata sul file.

Di seguito i link per scaricare il pdf della lezione ed il codice sorgente degli algoritmi di insertion sort e counting sort.

Download

Lezione 2: Algoritmi di Ordinamento: http://bit.ly/sU2tMs
countsor.c: http://bit.ly/vlz5eO
Insort.c: http://bit.ly/tCGbBy

La lezione si conclude qui, per qualsiasi chiarimento potete lasciare un commento in fondo alla pagina.L’indice delle lezioni si trova qui. La lezione precedente è stata Strutture dati elementari: Le liste.

Il prossimo appuntamento e’ per Venerdi’ 4 Novembre 2011, la lezione avra’ per argomento gli Alberi.

Alla prossima!

Puoi seguire Massimo Orazio Spata, l’autore di questo post, su Twitter.

Sei veramente bravo in qualcosa e desideri condividere questa conoscenza con gli altri? Stiamo cercando collaboratori per creare altri corsi nella Scuola Serale di Italian Geek. Se sei interessato, scrivici all’indirizzo:info@italiangeek.com