Insertion sort

L’insertion sort fa parte degli algoritmi di sorting. $\in O(n^2)$

Input Sequenza di $n$ valori $A=<a_0,a_1,...,a_{n-1}>$.

Output Permutazione $<a_0^{\prime },a_1^{\prime },...,a_{n-1}^{\prime }>$ della sequenza $A$ tale che $a_0^{\prime }\le a_1^{\prime }\le ...\le a_{n-1}^{\prime }$

title: Attenzione
Come costo computazionale calcoliamo i confronti eseguiti tra i valori di A.

1. si parte con il primo elemento che è ordinato, essendo l’unico
2. si prende l’elemento successivo, e si valuta con quello precedente. Se quello nuovo è maggiore allora si lascia dove è, se invece è minore si scambiano
3. fino a che non è il primo della lista, o è maggiore del precedente, si continua a spostare verso la testa

InsertionSort(A, n):
	for j=1 to n-1:
		i := j
		while i > 0 AND A[i] < A[i-1] do
			inverti A[i-1] e A[i]
			i := i - 1
		j := j + 1

Quindi quanti confronti si fanno? Fissato un j, si fanno al più j confronti, quindi si ha:

$$T(n)=\sum _{j=0}^{n-1}j=\frac{(n-1)n}{2}\in O(n^2)$$

asd_12