L’algoritmo di ordinamento InsertSort (ordinamento diretto) nasce dal concetto che per ordinare un array ordinato è sufficiente costruirne uno nuovo ordinato, inserendo gli elementi al posto giusto da subito. Nella pratica, non è necessario crearne uno nuovo ma dividere quello esistente in due parti, una ordinata e l’altra no.

Esempio:

Vogliamo ordinare l’insieme A = {5, 3, 2, 1, 4}.

Iterazione 1. A = {5 | 2, 3, 1, 4} → A = {2, 5 | 3, 1, 4}

Iterazione 2. A = {2, 5 | 3, 1, 4} → A = {2,3, 5 | 1, 4}

Iterazione 3. A = {2, 3, 5 | 1, 4} → A = {1, 2, 3, 5 | 4}

Iterazione 4. A = {1, 2, 3, 5 | 4} → A = {1, 2, 3,4, 5}

Codificando l’Insert Sort abbiamo:

1: per i = 2, 3,...,n ripeti 
	2: k = i −1 
	3: fintanto che k ≥ 1 e ak > ak+1 ripeti 
		4: scambia ak e ak+1 
		5: k = k −1 
	6: fine-ciclo 
7: fine-ciclo 

Nel caso migliore, ossia quando l’array ègia ordinato, il numero di operazioni svolte dall’algoritmo è dell’ordine di n.

Nel caso peggiore, il numero di operazioni eseguite dall’algoritmo è:

La complessità dell’algoritmo nel caso peggiore è quindi O(n ² ).

L’algoritmo Bubble Sort corregge il difetto principale del naïve sort, ossia il non accorgersi se l’array, a un certo punto, è già ordinato.

L’algoritmo è basato sullo scambio di elementi adiacenti. Ogni coppia di elementi adiacenti viene comparata e invertita di posizione se sono nell’ordine sbagliato. L’algoritmo itera questi passaggi, sulla porzione di array considerata, finché non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.

Deve il suo nome al modo in cui gli elementi vengono ordinati ossia quelli più piccoli “emergono” verso un’estremità della lista, così come fanno le bolle gassose in un bicchiere di acqua minerale; al contrario quelli più grandi “sprofondano” verso l’estremità opposta della sequenza.

Esempio

Abbiamo un array A = {3,5, 2, 4, 1} su cui applichiamo il bubble sort:

1. A = {3,5, 2, 4, 1} → A = {3,5,2, 4, 1} → A = {3, 2,5,4, 1} → A = {3, 2, 4,5,1} → A = {3, 2, 4, 1 | 5}

2. A = {3,2, 4, 1 | 5} → A = {2,3,4, 1 | 5} → A = {2, 3,4,1 | 5} → A = {2, 3, 1 | 4, 5}

3. A = {2,3, 1, | 4, 5} → A = {2,3,1 | 4, 5} → A = {2, 1 | 3, 4, 5}

4. A = {2,1 | 3, 4, 5} → A = {1, 2, 3, 4, 5}

Notare che, alla fine di ogni iterazione, l’elemento più grande del sottoinsieme ancora da ordinare, finisce in fondo alla sequenza, nella sua posizione definitivamente corretta, mentre la sottosequenza ancora in disordine si riduce di volta in volta di un elemento.

Codificando il Bubble Sort si ha:

1: flag = 1 
2: stop = n −1 
3: fintanto che flag = 1 ripeti
	 4: flag = 0 
	 5: per i = 1, 2,...,stop  ripeti 
		6: se ai > ai+1 allora 
			7: scambia ai e ai+1 
			8: flag = 1 
		9: fine-condizione 
	10: fine-ciclo 
	11: stop = stop −1 
12: fine-ciclo 

Anche in questo caso abbiamo due cicli annidati, ma, stavolta, l’algoritmo usa la variabile flag per terminare l’esecuzione, nel caso in cui l’insieme risulti ordinato.

Nel caso migliore, ossia quando l’insieme è già ordinato, l’algoritmo esegue un’unica scansione, quindi il numero di operazioni eseguite sarà dell’ordine di n.

Nel caso peggiore, alla prima iterazione vengono eseguite dunque sono necessarie n − 1 iterazioni del ciclo esterno per ordinare l’intera sequenza. Alla seconda n-2, e cosi via. Quindi il numero di operazioni svolte è:

Concludendo la complessità computazionale del Bubble Sort è di O(n ² ).

L’algoritmo naive sort, anche detto per selezione diretta o SelectionSort, ripete per n volte una procedura in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di scambiarlo con l’elemento che in quel momento occupa la posizione i-esima.

Ossia, alla prima iterazione verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione; alla seconda iterazione sarà selezionato il secondo elemento più piccolo dell’insieme ridotto (cioè costituito dagli elementi {a2,a3,…,an} ) e sarà scambiato con l’elemento che occupa la seconda posizione, e così via fino ad aver collocato nella posizione corretta tutti gli n elementi.

Considerando un vettore di n elementi l’algoritmo può essere codificato nel seguente modo :

per i = 1, 2,...,n ripeti
	per j = i +1,...,n ripeti
		se aj < ai allora
			scambia ai e aj
		fine-condizione
	fine-ciclo
fine-ciclo

Esempio

Supponiamo di applicare il naive sort al seguente array

A = {4, 2, 1, 3}

Ad ognuno dei passi dell’algoritmo, viene selezionato l’elemento più piccolo nella porzione di insieme ancora da ordinare, scambiandolo con l’elemento che si trova nella prima posizione di tale sottoinsieme.

i = 1 A = (4, 2,1, 3) → A = (1 | 2, 4, 3)

i = 2 A = (1 | 2, 4, 3) → A = (1, 2 | 4, 3)

i = 3 A = (1, 2, | 4,3) → A = (1, 2, 3 | 4)

i = 4 A = (1, 2, 3 | 4) → A = (1, 2, 3, 4)

Dopo 4 iterazioni, l’array sarà ordinato.

Per misurare le prestazioni dell’algoritmo (anche detta complessità) conteremo il numero di confronti.

Alla prima ripetizione del ciclo esterno vengono compiute n −1 operazioni con il ciclo interno; alla seconda ripetizione del ciclo esterno vengono eseguite n−2 operazioni con il ciclo interno, e così via fino a quando i = n.

Il numero di confronti totali sarà:

(N-1) + (N-2) + (N-3) + … + 2 + 1 = N*(N-1)/2 = O(N²)

Da notare che l’algoritmo fa gli stessi confronti sia per un array disordinato, sia per un array già ordinato, ossia per il naive sort non esiste un caso migliore o peggiore ma fa sempre tutti i confronti.

Viene usato quando l’insieme da ordinare è composto da pochi elementi e quindi, anche se non è molto efficiente, ha il vantaggio di non essere troppo difficile da implementare.