Problema dell’Ordinamento
Problema dell’ordinamento
• Formulazione del problema
– Si vuole ordinare una lista di elementi secondo una
data proprietà P
• Esempio:
– Dato il vettore V = {3,1,7,9,12,5,3,4,2,10} di N = 10
numeri interi, lo si ordini in modo tale che sia
verificata la proprietà:
• P = { V[i]  V[i+1]
 i=1, .. N-1}
Problema dell’ordinamento
• Il problema può essere risolto utilizzando diversi
algoritmi:
–
–
–
–
Ordinamento per scambi (Bubble Sort)
Ordinamento per Inserzioni
Ordinamento per distribuzione e fusione (Merge Sort)
Ordinamento con doppio indice (Quick Sort)
Ordinamento per Scambi
• L’algoritmo Bubble Sort prevede:
– il confronto e l’eventuale scambio degli elementi del
vettore per coppie;
– il confronto va iterato su tutti gli elementi della
sottolista da ordinare in modo da portare l’elemento
massimo nell’ultima posizione;
– dopo aver portato l’elemento massimo della
sottolista nell’ultima posizione vengono ripetute
ciclicamente le operazioni precedenti in modo da
ordinare le restanti sottoliste.
Ordinamento per Scambi
• I iterazione
– Situazione iniziale 
3 1 7 9 12 5 3 4 2 10
– I passo 
3 1 7 9 12 5 3 4 2 10
Confronto e scambio
– II passo 
1 3 7 9 12 5 3 4 2 10
Confronto
– Dopo il passo N 
Sottolista ordinata
1 3 7 9 5 3 4 2 10 12
Ordinamento per Scambi
• Iterazione k+1
– Dopo la k-esima iterazione
Sottolista ordinata
k-1
k
Ordinamento per Scambi
• Problema dello scambio
– Lo scambio può avvenire correttamente solo se si
utilizza una variabile di comodo
Passo 3
V[i]
C
Passo 1
V[i+1]
Passo 2
Frammento di codice
C = V[i+1];
V[i+1] = V[i];
V[i] = C;
Ordinamento per Scambi
• Ordinamento con l’algoritmo Bubble Sort
// Ciclo di ordinamento della sottolista
for ( j = 0; j < N; j++ )
{
// Scansione interna al sottoarray per collocare nella
// ultima posizione l’elemento massimo
for ( k = 0; k <= j; k++ )
{
if ( lista[k] > lista[j] ) // if (!P)
{
// Scambia i valori
scambio = lista[k];
lista[k] = lista[k+1];
lista[k+1] = scambio;
}
}
}
Ordinamento per Scambi
• Ottimizzazione dell’algoritmo
– L’algoritmo può essere ottimizzato se si considera che:
• L’ultimo scambio in un ciclo determina la sottolista ordinata.
Infatti, se l’ultimo scambio in una iterazione è avvenuto alla
posizione k, vuol dire che la sottolista di elementi da k+1 ad N
è ordinata, quindi la successiva iterazione dovrà riguardare gli
elementi da 1 a k.
– L’algoritmo può terminare anticipatamente qualora in
una iterazione non vi sono stati scambi.
Ordinamento per Scambi
• Complessità
– Numero di operazioni di confronto
• n(n-1)/2
– Complessità O(n2)
Ordinamento per Inserzioni
• L’algoritmo di ordinamento per inserzioni prevede:
– si considera l’elemento a[i]
– la ricerca del primo elemento più piccolo (a[k]) di quello
selezionato all’interno della sottolista da ordinare;
– l’inserimento dell’elemento a[k] al posto di a[i] e si scalano di
una posizione in avanti tutti gli elementi della sottolista fino a
quello immediatamente precedente a[k];
– Si intera il procedimento con l’elemento a[i+1].
Ordinamento per Inserzioni
• I iterazione
– Situazione iniziale 
3 9 7 1 12 5 3 4 2 10
– I passo 
3 9 7 1 12 5 3 4 2 10
– II passo 
3 7 9 1 12 5 3 4 2 10
– III Passo
Elementi da scalare di una posizione
1 3 7 9 12 5 3 4 2 10
// Ciclo di ordinamento della sottolista
for ( j = 0; j < N; j++ )
for ( k = j+1; k < N; k++ )
if ( lista[k] < lista[j] )
{
// Salvataggio del valore V[k]
c = V[k];
// Shift degli elementi di una posizione
for(i=k-1; i=>j; i--)
V[i+1] = V[i];
// Inserzione nella posizione j del valore precedentemente salvato
V[j] = c;
}
Ordinamento per Inserzioni
• Complessità
– L’algoritmo richiede n inserzioni . L’inserzione
dell’j-mo elemento al posto k richiede k-1 confronti e
j-k spostamenti, cioè j-1 operazioni (+
l’inserimento). Il numero di operazioni è quindi
n(n-1)/2
– Complessità O(n2)
Ordinamento con doppio indice
(Quick Sort)
• L’algoritmo Quick Sort prevede l’utilizzo dell’
– algoritmo di separazione
– Utilizzo ricorsivo dell’algoritmo di separazione sulle due
sottoliste fino a ordinare tutti gli elementi
Ordinamento con doppio indice (Quick Sort)
• L’algoritmo Quick Sort prevede l’utilizzo dell’
– algoritmo di separazione: tale algoritmo, tramite lo
spostamento fisico di al più 3 elementi per volta, tende a
raggiungere una situazione per cui:
• sia identificato un elemento di sparazione x
• siano identificate due sottoliste, una a sinistra ed una a
destra di x tali che:
– gli elementi della prima siano non maggiori di x
– gli elementi della seconda siano non minori di x
– l’algoritmo appena descritto viene ripetuto ricorsivamente
sulle due sottoliste fino a ordinare tutti gli elementi
Algoritmo di separazione
• Si partiziona l’array in modo che
– Si sceglie come elemento di partizione un
elemento (es. l’ultimo della lista) a[m]
– Si usa a[m] come elemento di separazione in
modo che
a[i]  a[m] per ogni i < m
a[i]  a[m] per ogni i > m
Algoritmo di Separazione
s
d c
9 1 6 4 5
8 2 3 0 6
s
0 1 6 4 5
d c
8 2 3 6 9
d c s
0 1 6 4 5
3 2 6 8 9
0 1 6 4 5
3 2 6 8 9
L1
L2
A[i]  A[8]
A[i]  A[8]
0 1 6 4 5
3 2 6 8 9
d s
c
0 1 6 4 5
3 2
d c
s
0 1 2 4 5
3 6
c
4 5
3 6
s
c
4 5
3
3 5
4
5
4
Ordinamento con doppio indice
• Passi dell’algoritmo di separazione
– si parta da una lista a[1]...a[n]
– si assume come elemento di separazione un qualsiasi
elemento dell’array x in posizione c (ad esempio
l’ultimo)
– si cerca il primo elemento da sinistra maggiore di x.
Supponiamo sia in posizione s (se tale elemento non
esiste si pone s = n+1)
– si cerca il primo elemento da destra minore di x.
Supponiamo sia in posizione d (se tale elemento non
esiste si pone d = 0)
Ordinamento con doppio indice
– si ordinano gli elementi trovati in modo che x
risulti al centro, a[d] vada alla sua sinistra e a[s]
vada alla sua destra. Nel caso s = n+1 o d = 0
viene effettuato l’ordinamento dei soli due
elementi trovati: a[c] e a[d] oppure a[s] e a[c]
– in questo momento risultano
• a[1]...a[s] formata da elementi non maggiori di x
• a[d]...a[n] formata da elementi non minori di x
Ordinamento con doppio indice
– sia c la nuova posizione dell’elemento di
separazione x, ottenuta tramite lo spostamento
precedente
– mentre s < d si riparte dal punto 3
dell’algoritmo, cercando da sinistra e da destra
a partire da s e da d
Int separa(int a[], int left, int right)
{
Int s = left –1;
Int d = right;
Int p = a[right];
Int temp;
for(;;) {
while (a[++s] >p && (s<right)) ;
while (p < a[- -d])
if (d = = left)
break;
if (s>=d)
break;
temp=a[s];
a[s]=a[d];
a[d]=temp;
}
temp=a[s];
a[s]=a[right];
a[right]=temp;
return s;
}
La routine quicksort
void quicksort(int lista[], int a, int z)
{
int cf = 0;
if(z>a)
{
cf = separa(lista, a, z);
quicksort(lista, a, cf-1);
quicksort(lista, cf+1, z);
}
}
Ordinamento per Distribuzione e Fusione
• L’algoritmo Merge Sort prevede 3 passi:
– Suddividi l’array in duw sottoarray
– ordina i sottoarray;
– esegui la fusione dei sottoarray ordinanti in un unico
vettore.
• Problema della fusione di due liste ordinate:
– Siano V1 e V2 due vettori ordinati di dimensione
rispettivamente N1 ed N2. Siano i e j gli indici
rispettivamente su V1 e V2. Il vettore fusione V si
otterrà con la seguente procedura:
• Si confrontano il primo elemento di V1 ed il primo elemento
di V2. L’elemento minore verra copiato in V, quindi verranno
incrementati gli indici k su V ed i su V1 se l’elemento minore
è stato ottenuto da V1, j su V2 se l’elemento minore è stato
ottenuto da V2;
• Si iterano i confronti finché non si raggiunge il termine di V1
o V2, quindi si completa il vettore fusione V con gli elementi
del vettore per il quale non si è giunti ancora al termine.
Fusione di due vettori ordinati
1
2 1
9 7
10 3
4 1
2
3
2 1
4 3
2 1
Nucleo della funzione merge:
void merge(V1,V2) {
i = j = 0;
// Ciclo di fusine delle due liste
while ((i < N1) && (j < N2))
{
// Confronto tra gli elementi di V1 e V2
if(V1[i] < V2[j])
// L’elemento copiato in V proviene da V1
V[k++] = V1[i++];
else
// L’elemento da inserire in V proviene da V2
V[k++] = V2[j++];
}
// Completamento del vettore V
if ( i < N1 )
// Il vettore V deve essere completato con gli elementi di V1
while (i < N1)
V[k++] = V1[i++];
else
// Il vettore V deve essere completato con gli elementi di V2
while (j < N2)
V[k++] = V2[j++];
}
}
Problema della distribuzione - Descrizione della
procedura sort:
– La suddivisione di una lista in sottoliste ordinate avviene in
questo modo:
• se la lista contiene più di due elementi viene calcolato il
punto medio della lista, vengono create due sottoliste a
partire da esso ed infine, viene richiamata ricorsivamente la
funzione di sort per entrambe le sottoliste create;
• se la lista è costituita da due elementi (condizione di uscita
dalla ricorsione), si procede con un confronto ed eventuale
scambio dei due elementi; questo garantisce la restituzione di
sottoliste ordinate.
Nucleo della procedura sort:
Void sort(V) {
if(Lunghezza > 2)
{
// La procedura separa divide la lista V in due
vettori V1 e V2
separa(V,V1,V2);
// Chiamate ricorsive su V1 e V2
sort(V1);
sort(V2);
// fusione delle liste
merge(V1,V2);
}
else
// Raggiunta la condizione di uscita dalla ricorsione
if(V[1] > V[2])
// Effettua lo scambio
{
scambio = V[1];
V[1] = V[2];
V[2] = V[1];
}
}
Merge Sort
Void mergesort(listaCompleta)
{
sort(listacompleta);
}