Insert Sort

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 2 ).

(Visited 1 times, 1 visits today)

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *