Sistemi e Tecnologie
Informatiche
Problemi di ordinamento
Umberto Ferraro Petrillo
Obiettivo della lezione

Presenteremo un semplice ed importante
problema da risolvere mediante
un approccio “ragionato”

Introdurremo le nozioni di algoritmo, struttura
dati ed efficienza di un algoritmo
Domanda …

Cosa rende un elenco telefonico di semplice
consultazione?
Risposta:
 I nominativi riportati sono elencati in ordine
alfabetico!

Come si ordina un elenco di nomi?
Problema
Compilazione di un elenco dei partecipanti al corso
e dei rispettivi voti (ordinato per cognome)









Zuzzurellone Zaira
Bamonte Giovanni
Romano Nadia
Medio Massimo
Del Monte Francesco
Rufolo Carmine
Donnaruma Giovanni
Santonastaso Maria
Abate Alfonso
24
26
21
28
30
19
27
25
27
Ordinamento di un elenco (ver. 1)
Elenco di partenza














Zuzzurellone Zaira
Bamonte Giovanni
Romano Nadia
Medio Massimo
Del Monte Francesco
Rufolo Carmine
Donnaruma Giovanni
Santonastaso Maria
Abate Alfonso
Elenco ordinato









Abate Alfonso
Bamonte Giovanni
Del Monte Francesco
Donnaruma Giovanni
Medio Massimo
Romano Nadia
Rufolo Carmine
Santonastaso Maria
Zuzzurellone Zaira
Individua il primo nominativo in ordine alfabetico nell’elenco di input
Riponi l’elemento individuato nella posizione 1 dell’elenco ordinato ed eliminalo
dall’elenco di partenza
Individua il primo nominativo in ordine alfabetico nell’elenco di input
Riponi l’elemento individuato nella posizione 2 dell’elenco ordinato ed eliminalo
dall’elenco di partenza
….
Procedura risolutiva
(prima versione)



Sia i l’indice della posizione attualmente considerata
(inizialmente i = 0)
Sia n la taglia dell’elenco da ordinare
Ripeti per n volte la seguente procedura:
 Scorri l’elenco di input ed individua il primo
nominativo in ordine alfabetico
 Riponi l’elemento individuato nella posizione i
dell’elenco ordinato ed eliminalo dall’elenco di
partenza
 Incrementa i di 1 (i = i +1)
Ordinamento di un elenco (ver 2)









Zuzzurellone Zaira
Donnaruma Giovanni
Romano Nadia
Medio Massimo
Del Monte Francesco
Rufolo Carmine
Bamonte Giovanni
Santonastaso Maria
Abate Alfonso
Cambiamo
Abate Alfonso con il
primo elemento
dell’elenco e
vice-versa









Abate Alfonso
Donnaruma Giovanni
Romano Nadia
Medio Massimo
Del Monte Francesco
Rufolo Carmine
Bamonte Giovanni
Santonastaso Maria
Zuzzurellone Zaira
Cambiamo
Bamonte Giovanni con
il secondo elemento
dell’elenco e
vice-versa









Abate Alfonso
Bamonte Giovanni
Romano Nadia
Medio Massimo
Del Monte Francesco
Rufolo Carmine
Donnaruma Giovanni
Santonastaso Maria
Zuzzurellone Zaira
Cambiamo
Del Monte Francesco
con il terzo elemento
dell’elenco e
vice-versa
Procedura risolutiva
(seconda versione)



Sia i l’indice della posizione attualmente considerata
(inizialmente i = 0)
Sia n la taglia dell’elenco da ordinare
Ripeti per n-1 volte la seguente procedura:
 Scorri l’elenco di input nella porzione da i ad n ed
individua il primo nominativo in ordine alfabetico
 Scambia l’elemento individuato con l’elemento
nella posizione i (se necessario)
 Incrementa i di 1 (i = i +1)
Algoritmo

Procedura di calcolo consistente in un insieme di passi
(istruzioni) e finalizzata alla risoluzione di un problema

E’ tipicamente descritto utilizzando il linguaggio naturale:
E.g. “Scorri l’elenco di input ed individua il primo
nominativo in ordine alfabetico”

Un algoritmo può essere implementato attraverso un
linguaggio di programmazione …

… tuttavia, esso non dipende da uno specifico linguaggio
di programmazione
Struttura dati

Le informazioni elaborate da un algoritmo sono definite dati
(e.g., elenco nominativi da ordinare)

I dati si possono presentare:
 in una forma elementare (e.g., il numero di studenti che segue la
lezione)
 in una forma strutturata (e.g, l’elenco degli studenti e delle loro
generalità)

Una struttura dati può godere di determinate proprietà utili a risolvere un
certo problema (e.g., l’elenco telefonico è ordinato alfabeticamente,
sono quindi in grado di cercare un nome velocemente)

La scelta di una particolare struttura dati influisce sull’efficienza di un
programma e sulla semplicità di realizzazione dello stesso
Implementazione di un algoritmo

L’elaborazione dei dati presuppone una loro
rappresentazione (e.g., numero telefonico
rappresentato come numero intero, nome di un
utente rappresentato come array di caratteri)
Rappresentazione dei dati
Problema: Fornire una rappresentazione in C/C++
dei dati sotto elencati









Zuzzurellone Zaira
Bamonte Giovanni
Romano Nadia
Medio Massimo
Del Monte Francesco
Rufolo Carmine
Donnaruma Giovanni
Santonastaso Maria
Abate Alfonso
24
26
21
28
30
19
27
25
27
Rappresentazione dei dati
Ipotesi 1:
Adoperiamo un array di taglia 3n
0
1
2
Zuzzurellone Zaira
24
3
4
Bamonte Giovanni
5
6
26
Romano
Ipotesi 2:
Adoperiamo una matrice di taglia nx3
0
1
2
0
Zuzzurellone
Zaira
24
1
Bamonte
Giovanni
26
2
Romano
Nadia
21
Rappresentazione dei dati
Ipotesi 3:
Adoperiamo 3 array distinti
0
1
2
Zuzzurellone
Bamonte
Romano
0
1
2
Zaira
Giovanni
Nadia
0
1
2
24
26
21
Rappresentazione dei dati
Ipotesi 4:
• Definiamo una classe studente
• Adoperiamo un array di taglia n di oggetti “studente”
0
1
2
Nome:
Zaira
Nome:
Zaira
Nome:
Zaira
Cognome:
Zuzzurellone
Cognome:
Zuzzurellone
Cognome:
Zuzzurellone
Voto:
24
Voto:
24
Voto:
24
Ordinamento di un elenco di
voti (Selection Sort)



Sia i l’indice della posizione attualmente considerata
(inizialmente i = 0)
Sia n la taglia dell’elenco da ordinare
Ripeti per n-1 volte la seguente procedura:
 Scorri l’elenco di input nella porzione da i ad n ed
individua il voto più alto
 Scambia l’elemento individuato con l’elemento
nella posizione i (se necessario)
 Incrementa i di 1 (i = i +1)
Ordinamento di un elenco di
voti (Selection Sort)
0
1
2
3
4
5
6
7
8
24
26
21
28
30
19
27
25
27
Scorriamo l’array
da 0 ad 8 per
individuare
il numero + alto
24
26
21
28
30
19
27
25
27
30
26
21
28
24
19
27
25
27
Il numero + alto
è 30, lo
scambiamo con
l’elemento alla
prima posizione
Scorriamo l’array
da 1 ad 8 per
individuare
il numero + alto
30
24
21
26
28
19
27
25
27
Il numero + alto è
28, lo scambiamo
con l’elemento
alla seconda
posizione
Ordinamento di un elenco di
voti (Selection Sort)
0
1
2
3
4
5
6
7
8
24
26
21
28
30
19
27
25
27
30
26
21
28
24
19
27
25
27
30
26
21
28
24
19
27
25
27
30
28
21
26
24
19
27
25
27
30
28
21
26
24
19
27
25
27
30
28
27
26
24
19
21
25
27
30
28
27
26
24
19
21
25
27
30
28
27
27
24
19
21
25
26
30
28
27
27
24
19
21
25
26
…
30
28
27
27
26
25
24
21
19
Votin [],
n){
Sia
Voti SelectionSort(int
l’elenco di input ed
la int
taglia
1 void
dello
stesso
2
3 int i, i_max;
Sia i l’indice dell’elemento attualmente considerato (i=0)
e4sia i_max l’indice dell’elemento massimo in Voti[i…n]
5
(i =n-1
0; ivolte
< n-1;lai++)
{
Ripeti
seguente
procedura
6 forper
7
Assumi
il valore nella posizione Voti[i] essere il
i_max
i;
8
massimo
nel=sottoelenco
Voti[i…n], (i = i_max)
//
ricerca
il
valore
massimo
in Voti[i..n]
9
j = i+1; j < Voti[i+1
n-1; j++) … n]
Cercafor
nel(int
sottoelenco
10
(Voti[j]
Voti[i_max])
11
il valoreif più
alto>ed
assegnane
i_max
= j;
// j è il nuovo i_max
12
l’indice ad
i_max
13
// scambia (se necessario) Voti[i_max] e Voti[i]
14
if (i != i_max) {
15
int temp
= Voti[i_max];
Se i_max
è diverso
da i, scambia
16
17
Voti[i] eVoti[i_max]
Voti[i_max]= Voti[i];
Voti[i] = temp;
18
}
19
20
21 }
22 }
23
i – Separa gli elementi
ordinati da quelli da
ordinare
j – Viene utilizzata per
scorrere gli elementi
da ordinare
temp – Serve come
variabile temporanea per
operare lo scambio
di due valori
i_max – Conserva l’indice
del valore piu’ alto
all’interno della porzione
di elenco non ordinata