Algoritmi e Strutture Dati
Capitolo 4
Ordinamento: Selection e Insertion Sort
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Ordinamento
Dato un insieme S di n oggetti presi da un
dominio totalmente ordinato, ordinare S
• 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
• È possibile effettuare ricerche in array ordinati in
tempo O(log n) (ricerca binaria)
2
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Il problema dell’ordinamento
(non decrescente)
• Input: una sequenza di n numeri <a1,a2,…,an>
• Output: una permutazione (riarrangiamento)
<ai1, ai2,…, ain> della sequenza di input tale che
ai1  ai2 … ain
3
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
SelectionSort
Approccio incrementale: estende l’ordinamento da k a k+1
elementi, scegliendo il minimo degli n-k elementi non
ancora ordinati e mettendolo in posizione k+1
4
7
2
4
5
3
1
1
2
3
4
5
7
1
2
4
5
3
7
1
2
3
4
5
7
1
2
4
5
3
7
1
2
3
4
5
7
1
2
3
5
4
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
SelectionSort (A)
1.
for k=0 to n-2 do
2.
m = k+1
3.
for j=k+2 to n do
4.
5.
NOTA: Assumiamo
che il primo elemento
dell’array sia in A[1]
if (A[j] < A[m]) then m=j
scambia A[m] con A[k+1]
• All’inizio del generico passo k, k=1,…, n-2, A[1],…,A[k] sono già
ordinati (all’inizio, ovvero per k=0, nulla è ancora ordinato)
• linee 2-4: ricerca del minimo fra gli elementi A[k+1],…,A[n] (m
mantiene l’indice dell’array in cui si trova il minimo presunto)
• linea 5: il minimo è spostato in posizione k+1
• alla fine del generico passo k, k=0,…, n-2, A[1],…,A[k+1] sono
ordinati
5
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Correttezza
• Si dimostra facendo vedere che alla fine del generico passo
k (k=0,…, n-2) si ha: (i) i primi k+1 elementi sono ordinati
e (ii) contengono i k+1 elementi più piccoli dell’array
• Induzione su k:
– k=0: Alla prima iterazione viene semplicemente selezionato
l’elemento minimo dell’array  (i) e (ii) banalmente verificate.
– k>0. All’inizio del passo k i primi k elementi sono ordinati e sono
i k elementi più piccoli nell’array (ipotesi induttiva). Allora la tesi
segue dal fatto che l’algoritmo seleziona il minimo dai restanti
n-k elementi e lo mette in posizione k+1. Infatti:
(ii) i k+1 elementi restano i minimi nell’array
(i) l’elemento in posizione k+1 non è mai più piccolo dei primi
k
6
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Complessità
temporale
SelectionSort (A)
1.
for k=0 to n-2 do
2.
m = k+1
3.
for j=k+2 to n do
4.
5.
1 assegnamento
if (A[j] < A[m]) then m=j
scambia A[m] con A[k+1]
n-2
n-k-1 confronti
(operaz. dominante)
1 scambio
(3 assegnamenti)
il tutto eseguito
n-1 volte
n-1
T(n) =  (n-k-1) =  k = n·(n-1)/2 =  (n2)
k=0
k=1
Si noti che T(n) è SEMPRE UGUALE ad un polinomio di 2º grado in n,
e quindi la notazione Θ è perfettamente ESPRESSIVA del valore di T(n)
 Tworst(n) = Tbest(n) = Tavg(n) =  (n2)
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
InsertionSort
Approccio incrementale: estende l’ordinamento da k a k+1
elementi, inserendo l’elemento in posizione k+1-esima
nella giusta posizione rispetto ai primi k elementi
8
7
2
4
5
3
1
2
4
5
7
3
1
2
7
4
5
3
1
2
3
4
5
7
1
2
4
7
5
3
1
1
2
3
4
5
7
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
InsertionSort (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
for j=1 to k+1 do
4.
5.
if (A[j] > x) then break
if (j < k+1) then
6.
for t=k downto j do A[t+1]= A[t]
7.
A[j]=x
•
•
•
•
•
9
All’inizio del generico passo k, A[1],…,A[k] sono già ordinati
elemento x=A[k+1] inserito nella posizione che gli compete
linee 3 e 4: individuano la posizione j in cui va messo x
linea 6: fa spazio per inserire x
Alla fine del generico passo k, A[1],…,A[k+1] sono ordinati
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Correttezza
• Si dimostra facendo vedere che alla fine del generico
passo k (k=1,…, n-1) i primi k+1 elementi sono ordinati
(si noti la differenza con il Selection Sort, in cui invece
dovevamo far vedere che erano i più piccoli)
• Induzione su k:
– k=1: banale: si riordinano A[1] e A[2];
– k>1: All’inizio del passo k i primi k elementi sono ordinati
(ipotesi induttiva). Allora la tesi segue dalla struttura
dell’algoritmo, il quale inserisce A[k+1] nella giusta posizione
rispetto alla sequenza A[1],…,A[k]
10
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Complessità temporale
InsertionSort (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
for j=1 to k+1 do
4.
if (A[j] > x) then break
5.
if (j < k+1) then
6.
for t=k downto j do A[t+1]= A[t]
7.
A[j]=x
j*≤k+1
confronti
k+1–j*
assegnamenti
k+1
oper.
il tutto eseguito
n-1 volte
n-1
T(n) =  (k+1) =  (n2)
k=1
Tworst(n) = Tbest(n) = Tavg(n) =  (n2)
Possiamo fare meglio?
11
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Una variante dell’IS più efficiente
InsertionSort2 (A)
1.
for k=1 to n-1 do
2.
x = A[k+1]
3.
j=k
4.
while j > 0 e A[j] > x do
5.
tk ≤ 2k
assegnam.
A[j+1] = A[j]
6.
j= j-1
7.
A[j+1]=x
n-1
n-1
T(n) =  tk ≤  2k
k=1
k=1
 T(n) = O(n2)
12
il tutto eseguito
n-1 volte
Si noti che T(n) è AL PIÙ
UGUALE ad un polinomio di 2º
grado in n, e quindi la notazione
O è perfettamente ESPRESSIVA
del valore di T(n)
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Caso migliore, peggiore, medio
• Caso migliore
– array già ordinato in ordine crescente  tk = 0
 Tbest(n) = (n) (costo del ciclo for esterno)
• Caso peggiore
– array ordinato in ordine decrescente  tk = 2k
n-1
 Tworst(n) =  2k = (n2)
• Caso medio
k=1
– array disordinato  il valore atteso di tk = k
n-1
 Tavg(n) =  k = (n2)
k=1
13

Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Complessità spaziale
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 del Selection Sort
e dell’Insertion Sort è Θ(n)
Nota: Se la complessità spaziale di un certo algoritmo è Θ(g(n)), e se tale
algoritmo “ispeziona” l’intera memoria occupata, allora la complessità
temporale dell’algoritmo è (g(n)).
14
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Conseguenze per il problema dell’ordinamento
La complessità spaziale di qualsiasi algoritmo che risolve il
problema dell’ordinamento è (n) (dimensione input)
…ma qualsiasi algoritmo che risolve il problema
dell’ordinamento deve ispezionare tutti i dati in ingresso, e
quindi ha complessità temporale T(n)=(n)

Il problema dell’ordinamento ha delimitazione inferiore
(lower bound) alla complessità temporale (n).
15
Copyright © 2004 - The McGraw - Hill Companies, srl
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Riepilogo
Caso T(n)
Caso Caso
migliore medio peggiore
S(n)
Selection Sort
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n)
Insertion Sort 1
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n2)
Θ(n)
Insertion Sort 2
Θ(n)
Θ(n2)
Θ(n2)
O(n2)
Θ(n)
16
Copyright © 2004 - The McGraw - Hill Companies, srl
Approfondimento: Algoritmo Bubble Sort
Definizione
Sia A=<a1,a2,… … an> una sequenza di n numeri. La coppia (ai,aj) è chiamata
inversione (rispetto ad un ordinamento crescente) se i <j ed ai > aj.
L’algoritmo Bubble Sort risolve il problema dell’ordinamento seguendo la
seguente strategia:
 1) Si scorre la sequenza A[1],… …,A[n], eliminando inversioni contigue (in tal
modo si porta il massimo degli n elementi considerati nella posizione A[n]);
 2) Si scorre la sequenza A[1],……,A[n-1], eliminando inversioni contigue (in
tal modo si porta il massimo degli n-1 elementi considerati nella posizione A[n1])
 n-1) Si scorre la sequenza A[1],A[2], eliminando inversioni contigue (in tal
modo si porta il massimo dei due elementi considerati nella posizione A[2]).
Fornire un’implementazione del Bubble Sort e analizzarne la complessità
computazionale.
Algoritmo Bubble Sort – Soluzione
Bubble-Sort-1(A)
limite  length(A)
for h 1 to (length(A)-1)
do for i 1 to (limite-1)
do if (A[i] > A[i+1])
then k  A[i]
A[i]  A[i+1]
A[i+1]  k
limite  limite - 1
L’algoritmo è corretto? SÌ! (dimostrazione analoga al Selection Sort)
Qual è la complessità temporale dell’algoritmo?
- linea (o il blocco di linee di codice) eseguito più volte
if (A[i] > A[i+1]) - operazione di confronto
- N. volte che viene eseguita
n2
n  h 

2
h1
n 1
-Notare- il numero di volte che questa linea viene eseguita
non dipende dall’ input  T(n)=(n2).
Algoritmi e strutture dati
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Esercizi di approfondimento per casa
Illustrare l’evoluzione di Insertion-Sort 2 applicata
all’array A=<31,41,59,26,41,58>
•
• Riscrivere la procedura Insertion-Sort 1 per
ordinare in modo non crescente
• Riscrivere la procedura Insertion-Sort 2 per
ordinare l’array da destra verso sinistra
19
Copyright © 2004 - The McGraw - Hill Companies, srl