Abilità Informatiche
Ingegneria Chimica
Lezione 18 del 18/04/2012
Prof. Antonino Stelitano
Docente Antonino Stelitano
Tutor
Lezioni Lunedì
Mercoledì
14:00 – 17:30 aula 16
15:45 – 19:00 aula 15
Lab. Paolo Ercoli – via Tiburtina 205
Ricevimento: Per appuntamento [email protected]
Sito web: http://w3.uniroma1.it/ab_informatiche
3
Algoritmi di ordinamento
° Gli algoritmi di ordinamento hanno lo scopo
di organizzare un insieme secondo una
relazione d'ordine stabilita.
° Il caso degli algoritmi di ordinamento è
particolarmente interessante, perché siamo di
fronte ad algoritmi che fanno la stessa cosa,
ma con complessità diversa.
° La complessità è proporzionale alle
dimensioni del problema, in questo caso al
numero n degli elementi che dobbiamo
ordinare.
° Vedremo due algoritmi di ordinamento:
Ordinamento per selezione (o
Selection Sort)
Ordinamento a bolle (o Bubble Sort)
A.Pi
nto
Selection Sort – L’Algoritmo
I passi da seguire sono i seguenti :
1) Posizionamento sul primo elemento dell’array
2) Ricerca dell’elemento più grande e scambio con il primo elemento dell’array
3) Posizionamento sul secondo elemento dell’array
4) Ricerca dell’elemento più grande tra gli N-1 elementi rimasti e scambio con il secondo elemento dell’array
5) Posizionamento sul terzo elemento dell’array
6) Ricerca dell’elemento più grande tra gli N-2 elementi rimasti e scambio con il terzo elemento dell’array
7) Tale procedimento viene ripetuto N-1 volte
Osservazione : Per implementare l’Algoritmo abbiamo bisogno di 2 indici :
Uno che tiene conto della posizione in cui si trova l’elemento da ordinare
( primo, secondo, terzo, … )
Uno che permette di scorrere l’array alla ricerca del valore maggiore
A.Pi
nto
Ordinamento per selezione
Esempio
vettore A
Passo 1
Passo 2
Passo 3
d c b a
b d a c
d b a c
d c a b
6
Ordinamento per selezione
(selection sort)
° Funzionamento generale
° cerca nell’array ancora da ordinare
l’elemento minimo
° porta tale elemento nella prima posizione
dell’array ancora da ordinare
20 35 18 8 14 41 3 39
3 35 18 8 14 41 20 39
7
Ordinamento per selezione (selection sort)
Quindi, per tutti gli elementi dell’array:
° si cerca il primo elemento minimo e lo si
porta in prima posizione, cioè in a[0]
° si cerca il secondo elemento minimo e lo si
porta in seconda posizione, cioè in a[1]
° si cerca il terzo elemento minimo e lo si porta
in seconda posizione, cioè in a[2]
…
° si cerca il k-esimo elemento minimo e lo si
porta in k-esima posizione, cioè in a[k]
…
° Si procede così fino a che tutti gli elementi sono
ordinati
20 35 18 8 14 41 3 39
3 35 18 8 14 41 20 39
8
Ordinamento per selezione (selection sort)
° L’individuazione dell’elemento minimo avviene scandendo tutto l’array (parte non ancora ordinata dell’array)
° Prima della prima iterazione va inizializzata la variabile min
° si assegna a min il primo elemento dell’array a[0]
° Per tutti gli elementi
° confronta min con l’elemento corrente a[i]
° se a[i] è minore di min, poni a[i] in min
° Scambia min con a[i]
° Dobbiamo memorizzare l’indice del minimo
20 35 18 8 14 41 3 39
9
° Algoritmo di ricerca del minimo
min= a[0]
i_min=0
for (j = 1; j < n; j++)
if (a[j] < min)
{
min= a[j];
i_min=j;
}
° Scambio di min e a[0]
a[i_min] = a[0];
a[0]= min;
10
° La ricerca deve essere ripetuta per cercare
il secondo elemento minimo, poi il terzo,
il quarto, etc. fino ad arrivare all’elemento
(n-1) che a quel punto sarà
automaticamente ordinato
° la ricerca del secondo elemento avverrà a
partire dal secondo elemento (il primo è
già ordinato)
° la ricerca del terzo elemento avverrà a
partire dal terzo elemento ………
° quindi se ho ordinato i elementi cerco
l’elemento più piccolo a partire
dall’elemento i+1
° ad ogni iterazione cerco il minimo che
sposto in posizione (i+1)-esima
11
° Per tutti gli elementi a[i] del vettore
° min= a[i]
° cerca il minimo a partire dell’elemento a[i+1] nella parte non ordinata da (i+1) alla fine del vettore)
° cerca l’elemento più piccolo confrontandolo con min
° quando individuato scambialo con min e memorizza la sua posizione i_min
° scambia min con a[i]
° L’ultimo elemento è automaticamente ordinato,
° ciclo esterno da 0 a n-2
° ciclo interno a partire i+1 fino a n-1
° Per evitare un certo numero di assegnazioni, non memorizziamo il minimo in min, tanto abbiamo il suo indice
12
void SelectionSort (int A[ ], int n)
{
int i, j , i_min;
int temp;
for (i=0; i < n-1; i++)
{
i_min = i; /* cerca il minimo nella parte
non ordinata */
for (j = i+1; j< n ; j++)
if (A[j] < A[i_min])
i_min=j;
if (i != i_min) {
temp = A[i_min];
A[i_min] = A[i];
A[i] = temp; }
}
}
13
Complessità selection sort
° Istruzione dominante
° Istruzione ripetuta più volte
for (i = 0; i < n-1; i++)
{……………...
for (j =i+1; j< n ; j++)
if (A[j] < A[i_min])
i_min=j;
……….
° Il corpo del for esterno viene eseguito n -1 (ordine di n)
° Il for interno viene eseguito circa n volte per ogni ciclo esterno
° Complessità: O(n2)
° I cicli sono eseguiti un numero di volte che non dipende dalla particolare configurazione dei dati di ingresso.
° stesso costo per ogni possibile configurazione dei dati di ingresso;
° O(n2) anche se l'array è già completamente ordinato
14
Ordinamento a bolle (Bubble Sort)
° Si basa sul confronto (ed eventuale scambio)
successivo di due elementi contigui in cui il
più leggero viene spinto indietro (indice più
basso)
° Confronto tra le ultime due posizioni (n-1 e
n-2)
° si muove indietro il più leggero (verso
indice più basso)
° l’elemento più piccolo viene spinto in
prima posizione
° Alla fine della prima scansione (sono stati
analizzati n elementi) è stato ordinato un
elemento: l’elemento più leggero (che si trova
in posizione 0)
° Rimangono da ordinare gli altri (n-1)
elementi.
° Non considero più l’elemento ordinato
15
Ordinamento a bolle (Bubble Sort)
° L’iterazione del procedimento porterà in
seconda posizione (indice 1) il successivo elemento più leggero
° Rimangono gli ultimi (n-2) ancora da ordinare.
° La ripetuta applicazione di questa procedura porterà all'ordinamento totale dell'array.
° Due cicli:
° un ciclo esterno: viene cercato l'elemento i da spostare indietro. Si devono ancora ordinare (n-i) elementi
° un ciclo interno: che scorre la porzione di array alla ricerca dell'elemento più leggero.
° Il metodo degli scambi ripetuti garantisce che ad ogni passaggio sia ordinato un elemento
--> per n elementi, servono n-1 passaggi
16
30 12 18 8 14 41 3 39
30 12 18 8 14 41 3 39
30 12 18 8 14 3 41 39
30 12 18 8 3 14 41 39
30 12 18 3 8 14 41 39
30 12 3 18 8 14 41 39
30 3 12 18 8 14 41 39
3 30 12 18 8 14 41 39
17
° Iterando su tutta la lunghezza dell’array (meno 1 perché l’ultimo elemento è automaticamente ordinato)
(for ( i=0; i < n-1 ; i++))
° Per tutte le coppie contigue dell’array (a partire j=n-2 e j=n-1)
° Se la coppia corrente non è ordinata, scambia tra loro gli elementi
° if (a[j] < a[j-1]) scambia la coppia
° Loop interno:
° deve operare solo sulla parte che non ancora ordinata
° è legato al ciclo esterno:
° varia da n-1 a i (dove i e’ l’indice del ciclo esterno)
18
void BubbleSort (int A[ ], int n) {
int i, j;
int temp;
for (i =0 ; i < n-1; i++)
for (j = n-1 ; j > i ; j--)
if (A[j] < A[j-1]) {
temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
}
}
19
Algoritmo ottimizzato
° L’array può risultare ordinato prima
della fine del ciclo esterno.
° Si può inserire un controllo per evitare
di fare operazioni inutili:
° controllo di una variabile booleana
legata all’avvenuto scambio di
elementi
° quando una scansione dell'array
non causa nessuno scambio, vuol
dire che l'array è ordinato.
° alla fine di ogni ciclo interno, si
controlla il valore della variabile
booleana per verificare se
all’interno della scansione siano
stati o meno effettuati scambi.
20
Algoritmo ottimizzato
Descrizione dell’algoritmo:
Finché l'array non è ancora ordinato
° trovato=1
° per tutte le coppie contigue nella parte dell'array non ordinata
° se la coppia di elementi di elementi non è ordinata scambiare gli elementi della coppia
trovato = 0
21
Algoritmo Bubble Sort ottimizzato
void BubbleSort (int A[ ], int n)
{
int i=0, j, temp, ordinato;
do {
ordinato = 1;
for (j = n-1 ; j > i ; j--)
if (A[j] < A[j-1])
{
temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
ordinato = 0;
}
i++;
} while (!ordinato && i < n-1);
}
22
Complessità bubble sort
° Dipende dalla configurazione dei dati di ingresso.
° Caso migliore
° se l'array di ingresso fosse già ordinato l'algoritmo compirebbe una sola scansione con nessuno scambio
° costo di esecuzione: O(n).
° Caso peggiore
° sono necessarie n - 1 fasi per completare la sua esecuzione (il vettore è ordinato in senso inverso)
° Proporzionale a n il ciclo interno
° costo di esecuzione: O(n2)
° Si noti che è O(n2) solo nel caso peggiore, mentre il selection sort è sempre O(n2)
Top Related