Problema dell’ordinamento
Input: Sequenza di n numeri <a1,a2, ……,an>
Output: Permutazione
<a1,a2, ……,an> = <a1’,a2’, ……,an’>
π
tale che:
a1’  a2’  ……  an’
• Esempi: ordinare una lista di nomi alfabeticamente,
o un insieme di numeri, o un insieme di compiti
d’esame in base al cognome dello studente
• Subroutine in molti problemi
• E’ possibile effettuare ricerche in array ordinati in
tempo O(log n)
Insertion sort
Insertion sort = Algoritmo di ordinamento
Insertion-Sort(A)
A = array che contiene
la sequenza da
For j  2 to length[A]
ordinare
do
k  A[j]
i j–1
while i > 0 e A[i] > k
do
A[i+1]  A[i]
i i–1
A[i+1]  k
L’ insertion sort descrive in maniera formale la
procedura con cui ordiniamo una mano di carte da gioco:
• L’ indice j indica la carta corrente. L’ elemento A[j] è
copiato nella variabile k;
• Gli elementi A[1 … j-1] rappresentano le carte già
ordinate;
• Confrontiamo k = A[j] con tutti gli elementi A[1 … j-1]
partendo da j-1;
• Gli elementi più grandi di k vengono uno ad uno
spostati “a destra” fino a che non troviamo la giusta
posizione della carta corrente.
Insertion sort
Insertion sort = Algoritmo di ordinamento
A = array che contiene
Insertion-Sort(A)
la sequenza da
For j  2 to length[A]
ordinare
do
k  A[j]
i j–1
while i > 0 e A[i] > k
do
A[i+1]  A[i]
i i–1
A[i+1]  k
Esempio
input: A = <5,2,4,6,1,3>
j= 2
524613

254613
j= 3
254613

245613
j= 4
245613

245613
j= 5
245613

124563
j= 6
124563

123456
Notare: L’algoritmo di insertion sort è corretto!
(si dimostra banalmente per induzione)
Analisi di Insertion sort
Costo N.volte
Insertion-Sort(A)
For j  2 to length[A]
do
c1
n- 1
k  A[j]
c2
n -1
i j–1
c3
n -1
while i > 0 e A[i] > k
do
n
t
c4
j 2
n
A[i+1]  A[i] c5
i i–1
A[i+1]  k
j
 t
1
 t
1
j
j2
n
c6
j2
c7
j
n -1
tj = numero di volte che, per un fissato j, viene
eseguito il test del ciclo while (dipende dall’ input).
T(n) = tempo di esecuzione dell’algoritmo.
n
T n   c1 n  1  c2 n  1  c3 n  1  c4  tj 
j2
n


n


 c5  tj  1  c6  tj  1  c7 n  1
j2
j2


Analisi di Insertion Sort
Espressione generale
n
T n   c1 n  1  c2 n  1  c3 n  1  c4  tj 
j2
n


n


 c5  tj  1  c6  tj  1  c7 n  1
j2
j2
Caso migliore - A=<a1,a2, …,an> ordinata non decrescente
tj  1 ;
j = 2, 3, ……,n 
 n
 tj  n  1
 j2
 n

tj  1  0

 j2



Tbest n   c1  c2  c3  c4  c7  n  c1  c2  c3  c4  c7 
Il tempo di esecuzione è una funzione lineare della
dimensione dell’ input n, cioè Tbest(n)=O(n)
Nota: è anche vero che Tbest(n)=Ω(n), e quindi
Tbest(n)=Θ(n)
Analisi di Insertion Sort
Espressione generale
n
T n   c1 n  1  c2 n  1  c3 n  1  c4  tj 
j2
n


n


 c5  tj  1  c6  tj  1  c7 n  1
j2
j2
Caso peggiore - A=<a1,a2, …,an> ordinata decrescente
tj  j ; j= 2, 3, …… , n
n(n  1)
 n
t

1
 j
2
 j 2
 n
n(n  1)

t

1

j

2
j

2





c  c5  c6 
n2 
Tworst n   c4  c5  c6 
  c1  c2  c3  c7  4
n 
2 
2

 c1  c2  c3  c4  c7 
Il tempo di esecuzione è una funzione quadratica
della dimensione dell’ input n, cioè Tworst(n)=O(n2)
Nota: è anche vero che Tworst(n)=Ω(n2), e quindi
Tworst(n)=Θ(n2)
Analisi di Insertion Sort
Espressione generale
n
T n   c1 n  1  c2 n  1  c3 n  1  c4  tj 
j2
n


n


 c5  tj  1  c6  tj  1  c7 n  1
j2
j2
Caso medio - A=<a1,a2, …,an> casuale
In media
tj = j/2 ; j= 2, 3, …… , n

Il tempo di esecuzione è una funzione quadratica
della dimensione dell’ input n, cioè Tavg(n)=Θ(n2)
Ricordiamo che oltre alla complessità temporale
dobbiamo valutare anche la complessità spaziale di
un algoritmo, ovvero lo spazio di memoria
necessario per ospitare le strutture di dati
utilizzate dall’algoritmo.
La complessità spaziale dell’Insertion Sort è Θ(n)
Notare
Se la complessità spaziale di un certo algoritmo è
(g(n)) e tale algoritmo per sua natura è
costretto ad “ispezionare” l’intero input,
allora la complessità temporale dell’algoritmo è
(g(n)).
Conseguenze:
• Nel caso dell’Insertion Sort:
T(n) = (S(n))
dove
T(n) = compl.temp
S(n) = compl.spaziale
• La complessità spaziale di qualsiasi algoritmo
che risolve il problema dell’ordinamento è (n).

• Qualsiasi algoritmo che risolve il problema
dell’ordinamento ha complessità temporale
T(n)=(n)
Esercizi di approfondimento
• Illustrare l’evoluzione di Insertion-Sort
applicata all’array A=<31,41,59,26,41,58>
• Riscrivere la procedura di Insertion-Sort per
ordinare in modo non crescente
Reverse Insertion-Sort(A)
For j  2 to length[A]
do
k  A[j]
i j–1
while i > 0 e A[i] < k
do
A[i+1]  A[i]
i i–1
A[i+1]  k