Algoritmi di ordinamento - Università degli Studi di Brescia

Alcuni metodi di ordinamento
Algoritmi di ordinamento
• Ordinamento per inserimento diretto
(insertion sort)
• Ordinamento per selezione (selection sort)
• Ordinamento “a bolle” (bubble sort)
Fondamenti di Informatica A
Ingegneria Gestionale
Università degli Studi di Brescia
Docente: Prof. Alfonso Gerevini
Ordinamento
per inserimento diretto
2
Fondamenti di Informatica A – Università di Brescia
Docente: A. Gerevini
Ordinamento
per inserimento diretto
Idea di base
1) si considera il secondo elemento e lo si inserisce nella prima posizione se
risulta minore del primo elemento. Se non è minore del primo elemento
rimane dov’è.
44
55
12
42
94
18
44
55
12
42
94
18
2) si considera il terzo elemento e lo si inserisce nella prima o nella seconda
posizione, a seconda che sia minore del primo o del secondo elemento. Se
non è minore di nessuno dei due rimane dov’è
12
44
55
42
94
18
12
42
44
55
94
18
3) si considera il quarto elemento e lo si inserisce nella prima o nella
seconda o nella terza posizione, a seconda che sia minore del primo o del
secondo o del terzo elemento. Se non è minore di nessuno dei due rimane
dov’è.
12
42
44
55
94
18
12
18
42
44
55
94
44
… e così via fino a considerare tutti gli elementi
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
3
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
4
inizio
Inserimento
diretto
i←1
n ← 100
fine
no
• Supponiamo all’inizio di avere il vettore a seguente
Ipotesi:
i<n
supponiamo di
considerare un
vettore di 100
elementi indicizzati
da 0 a 99
sì
x ← a[i]
j←i-1
(j>=0) AND
(x < a[j])
sì
no
a[j+1] ← x
i←i+1
a[j+1] ← a[j]
j←j-1
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
Come funziona?
5
a
Passi di ordinamento:
1. n = 6
(supponiamo che il numero di elementi significativi sia 6)
2. i = 1
3. x = a[1] = 55
4. j = i – 1 = 0
5. Controllo se ((j >=0) && (x < a[0])) Î non è vero
(x vale 55 ed a[0] vale 44)
6. a[j+1] = x = 55
Docente: A. Gerevini
Esecuzione (continua…)
7.
8.
9.
10.
11.
12.
13. Controllo se ((j >=0) && (x < a[0])) Î è vero (x vale 12 ed a[0] vale 44)
14. a[1] = a[0] = 44
a 44 44 55 42 94 18
15. j = j – 1 = -1
Docente: A. Gerevini
55 42 94 18
Fondamenti di Informatica A – Università di Brescia
Fondamenti di Informatica A – Università di Brescia
6
Esecuzione (continua…)
i=i+1=2
x = a[2] = 12
j=i–1=1
Controllo se ((j >=0) && (x < a[1])) Î è vero (x vale 12 ed a[1] vale 55)
a[2] = a[1] = 55
a 44 55 55 42 94 18
j = j –1 = 0
16. Controllo se ((j >=0) && (x < a[-1])) Î non è vero
17. a[0] = x = 12
a 12 44
18. i = i + 1 = 3
44 55 12 42 94 18
0 1 2 3 4 5
7
19.
20.
21.
22.
23.
24.
25.
26.
x = a[3] = 42
j=i–1=2
Controllo se ((j >=0) && (x < a[2])) Î è vero (x vale 42 ed a[2] vale 55)
a[3] = a[2] = 55
a 12 44 55 55 94 18
j=j–1=1
Controllo se ((j >=0) && (x < a[1])) Î è vero (x vale 42 ed a[1] vale 44)
a[2] = a[1] = 44
a 12 44 44 55 94 18
j=j–1=0
27.
28.
29.
30.
31.
Controllo se ((j >=0) && (x < a[0])) Î non è vero (x vale 42 ed a[0] vale 12)
a[1] = x = 42
a 12 42 44 55 94 18
i=i+1=4
x = a[4] = 94
j=i–1=3
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
8
Esecuzione (continua…)
Esecuzione (continua…)
32. Controllo se ((j >=0) && (x < a[3])) Î non è vero (x vale 94 ed a[3] vale 55)
44. a[3] = a[2] = 44
33. a[4] = x = 94
45. j = j – 1 = 1
a
12 42 44 55 94 18
a
12 42 44 44 55 94
34. i = i + 1 = 5
46. Controllo se ((j >=0) && (x < a[1])) Î è vero (x vale 18 ed a[1] vale 42)
35. x = a[5] = 18
47. a[2] = a[1] = 42
36. j = i – 1 = 4
48. j = j – 1 = 0
a
12 42 42 44 55 94
37. Controllo se ((j >=0) && (x < a[4])) Î è vero (x vale 18 ed a[4] vale 94)
49. Controllo se ((j >=0) && (x < a[0])) Î non è vero (x vale 18 ed a[0] vale 12)
38. a[5] = a[4] = 94
50. a[1] = x = 18
39. j = j – 1 = 3
a
12 42 44 55 94 94
a
51. i = i + 1 = 6
40. Controllo se ((j >=0) && (x < a[3])) Î è vero (x vale 18 ed a[3] vale 55)
52. Controllo se i < 6 Î non è vero
41. a[4] = a[3] = 55
42. j = j – 1 = 2
53. Fine
a
12 42 44 55 55 94
12 18 42 44 55 94
ORDINATI!
43. Controllo se ((j >=0) && (x < a[2])) Î è vero (x vale 18 ed a[2] vale 44)
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
9
Docente: A. Gerevini
Programma di ordinamento per
inserimento diretto
Fondamenti di Informatica A – Università di Brescia
10
Ordinamento per selezione
Idea di base
main(); /* ordinamento per inserimento diretto */
{ int a[100];
int i, j, x, n;
n = 100;
for (i=1;i<n;i++)
{
x=a[i]; j=i-1;
while ((j>=0) && (x < a[j]))
{
a[j+1]=a[j];
j:=j-1;
}
a[j+1]=x;
}
}
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
1) scambio il primo elemento con il più piccolo
2) scambio il secondo elemento con il secondo più piccolo
3) scambio il terzo elemento con il terzo più piccolo
…
11
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
12
inizio
Ordinamento per selezione
i←0
n ← 100
no
44
55
12
42
94
18
12
55
44
42
94
18
12
18
44
42
94
55
12
18
42
44
94
55
12
18
42
44
94
55
12
18
42
44
55
Ordinamento
per selezione
i<n-1
sì
fine
k←i
x ← a[i]
j ← i +1
no
j<n
sì
94
k ←j
x ← a[j]
44
sì
a[j]<x
a[k] ← a[i]
a[i] = x
i←i+1
no
j ← j +1
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
13
Docente: A. Gerevini
Come funziona?
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
44 55 12 42 94 18
0 1 2
3 4 5
Passi di ordinamento:
1. n = 6
(supponiamo che il numero di elementi significativi sia 6)
2. i = 0
3. Controllo se i < 5 Î è vero
4. k = i = 0
5. x = a[0] = 44
6. j = i + 1 = 1
7. Controllo se j < 6 Î è vero
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
14
Esecuzione (continua…)
• Supponiamo all’inizio di avere il vettore a seguente
a
Fondamenti di Informatica A – Università di Brescia
15
Controllo se a[1] < x Î non è vero
j=j+1=2
Controllo se j < 6 Î è vero
Controllo se a[2] < x Î è vero
k=j=2
x = a[j] = 12
j=j+1=3
Controllo se j < 6 Î è vero
Controllo se a[3] < x Î non è vero
j=j+1=4
Controllo se j < 6 Î è vero
Controllo se a[4] < x Î non è vero
j=j+1=5
Controllo se j < 6 Î è vero
Docente: A. Gerevini
(a[1] vale 55 e x vale 44)
(a[2] vale 12 e x vale 44)
(a[3] vale 42 e x vale 12)
(a[4] vale 94 e x vale 12)
Fondamenti di Informatica A – Università di Brescia
16
Esecuzione (continua…)
22.
23.
24.
25.
26.
Controllo se a[5] < x Î non è vero
j=j+1=6
Controllo se j < 6 Î non è vero
a[k] = a[i] = a[2] = 44
a[i] = x = 12
25.
26.
27.
28.
29.
30.
31.
32.
33.
i=i+1=1
k=i=1
x = a[i] = 55
j=i+1=2
Controllo se j < 6 Î è vero
Controllo se a[2] < x Î è vero
k=j=2
x = a[j] = 44
j=j+1=3
Docente: A. Gerevini
Esecuzione (continua…)
(a[5] vale 18 e x vale 12)
a
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
12 55 44 42 94 18
(a[2] vale 44 e x vale 55)
Fondamenti di Informatica A – Università di Brescia
17
12 18 44 42 94 55
Fondamenti di Informatica A – Università di Brescia
(a[4] vale 94 e x vale 42)
(a[5] vale 18 e x vale 42)
Fondamenti di Informatica A – Università di Brescia
18
main(); /* ordinamento per selezione
{ int a[100];
int i, j, k, x, n;
n = 100;
for (i=0;i<n-1;i++)
{
k=i; x=a[i];
for (j=i+1;j<n;j++)
{ if (a[j] < x)
{
k=j;
x=a[j];
}
}
a[k]=a[i];
a[i]=x;
}
48. a[k] = a[5] ← a[i] = a[1] = 55
49. a[i] ← x = 18 ………… eccetera eccetera… completare per esercizio
Docente: A. Gerevini
Docente: A. Gerevini
(a[3] vale 42 e x vale 44)
Programma di ordinamento per
selezione
Esecuzione (continua…)
a
Controllo se j < 6 Î è vero
Controllo se a[3] < x Î è vero
k=j=3
x = a[3] = 42
j=j+1=4
Controllo se j < 6 Î è vero
Controllo se a[4] < x Î non è vero
j=j+1=5
Controllo se j < 6 Î è vero
Controllo se a[5] < x Î è vero
k=j=5
x = a[5] = 18
j=j+1=6
Controllo se j < 6 Î non è vero
19
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
20
Bubble sort
Bubble sort
Idea di base
44
55
12
42
94
18
1) L’algoritmo confronta coppie di elementi successivi (con indice j e j - 1)
e se occorre li scambia ponendo il minore nella posizione j – 1
12
44
55
18
42
94
2) Alla fine della prima passata dell’intero vettore, l’elemento più piccolo
si trova nella prima posizione
12
18
44
55
42
94
12
18
42
44
55
94
12
18
42
44
55
94
12
18
42
44
55
94
3) Alla seconda passata vengono esaminati solo n-1 elementi e l’elemento
più piccolo viene a trovarsi nella seconda posizione
4) Alla terza passata si esaminano n-2 elementi, etc. etc.
5) Alla fine della n-1-esima passata gli elementi sono ordinati
44
Fondamenti di Informatica A – Università di Brescia
Docente: A. Gerevini
21
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
22
inizio
‘Bubble sort’
i←0
n ← 100
no
fine
Come funziona?
a
i<n-1
sì
Passi di ordinamento:
1. n = 6
(supponiamo che il numero di elementi significativi sia 6)
2. i = 0
3. Controllo se i < 5 Î è vero
4. j = n –1 = 5
5. Controllo se j > i Î è vero
6. Controllo se a[4] > a[5] Î è vero
(a[4] vale 94 e a[5] vale 18)
7. x = a[4] = 94
8. a[4] = a[5] = 18
a 44 55 12 42 18 94
9. a[5] = 94
j←n-1
no
j>i
sì
sì
x ← a[j-1]
a[j-1] ← a[j]
a[j] ← x
44 55 12 42 94 18
0 1 2 3 4 5
i←i+1
a[j-1]>a[j]
no
j ← j -1
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
23
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
24
Esecuzione (continua…)
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
j = j –1 = 4
Controllo se j > i Î è vero
Controllo se a[3] > a[4] Î è vero
x = a[3] = 42
a[3] = a[4] = 18
a
a[4] = 42
j = j –1 = 3
Controllo se j > i Î è vero
Controllo se a[2] > a[3] Î non è vero
j = j –1 = 2
Controllo se j > i Î è vero
Controllo se a[1] > a[2] Î è vero
x = a[1] = 55
a
a[1] = a[2] = 12
a[2] = 55
(a[3] vale 42 e a[4] vale 18)
44 55 12 18 42 94
(a[2] vale 12 e a[3] vale 18)
(a[1] vale 55 e a[2] vale 12)
44 12 55 18 42 94
Fondamenti di Informatica A – Università di Brescia
Docente: A. Gerevini
Esecuzione (continua…)
25
Programma ‘Bubble sort’
main(); /* ordinamento a bolle
{ int a[100];
int i, j, x, n;
n = 100;
for (i=0;i<n-1;i++)
{
for (j=n-1;j>i;j--)
if (a[j-1] > a[j])
{
x=a[j-1];
a[j-1]=a[j];
a[j]=x;
}
}
}
Docente: A. Gerevini
Fondamenti di Informatica A – Università di Brescia
27
25.
26.
27.
28.
29.
30.
j = j –1 = 1
Controllo se j > i Î è vero
Controllo se a[0] > a[1] Î è vero
x = a[0] = 44
a[0] = a[1] = 12
a[1] = 44
31.
32.
j = j –1 = 0
Controllo se j > i Î non è vero
33.
34.
35.
36.
37.
i=i+1=1
Controllo se i < 5 Î è vero
j=n–1
Controllo se j > i Î è vero
Eccetera… eccetera… per esercizio
Docente: A. Gerevini
(a[0] vale 44 e a[1] vale 12)
a
12 44 55 18 42 94
FINE PRIMA PASSATA
PROSSIMA PASSATA
da j = 5 fino a i = 1
Fondamenti di Informatica A – Università di Brescia
26