Algoritmi di ordinamento Calzetta Emilia Cervone Vincenzo Didattica della programmazione I Prof....
-
Upload
palmiro-casali -
Category
Documents
-
view
214 -
download
0
Transcript of Algoritmi di ordinamento Calzetta Emilia Cervone Vincenzo Didattica della programmazione I Prof....
Algoritmi di ordinamentoAlgoritmi di ordinamento
Calzetta Emilia Calzetta Emilia
Cervone Vincenzo Cervone Vincenzo
Didattica della programmazione IDidattica della programmazione I Prof. Giulio GiuntaProf. Giulio Giunta
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Contenuti:Contenuti:
Algoritmi di ordinamento iterativi e ricorsiviOrdinamento per inserimento: Insertion-sort Ordinamento per inserimento: Insertion-sort
Ordinamento per selezione del min/max: Selection-sort Ordinamento per selezione del min/max: Selection-sort
Ordinamento a bolle: Bubble-sortOrdinamento a bolle: Bubble-sort
Analisi della complessità nel contare gli scambi e i confronti Analisi della complessità nel contare gli scambi e i confronti (caso peggiore)(caso peggiore)
Analisi comparataAnalisi comparata
Simulazioni in linguaggio VBSimulazioni in linguaggio VB
Riferimenti:Riferimenti:Cormen, Leiserson, Rivest- Introduzione agli algoritmi -Cormen, Leiserson, Rivest- Introduzione agli algoritmi -McGrawHillMcGrawHill
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Classe:Classe: 3^ I.T.I.S.3^ I.T.I.S.
Prerequisiti:Prerequisiti:Conoscenze sull’organizzazione dei dati mediante la struttura vettorialeConoscenze della teoria della ricorsione e dell’iterazioneConoscenze della teoria e implementazione degli algoritmi Conoscenze del linguaggio Visual Basic e delle Macro di Excel
Obiettivi:Obiettivi:Saper gestire l’organizzazione e ordinamento dei dati in un vettoreCapire l’importanza dell’ordinamento dei dati Utilizzare le strutture di iterazione e ricorsioneAnalizzare le applicazioni relative agli argomenti teorici affrontati
Modalità di lavoro:Modalità di lavoro:lezioni frontaliutilizzo del laboratorio
44
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Ordinamento di una sequenzaOrdinamento di una sequenzaUna sequenza è un insieme di elementi omogenei tra loro. Ordinare una sequenza di elementi in ordine crescente (non-decrescente) significa disporre gli elementi in modo da averli in ordinati in base al loro valore dal più piccolo al più grande da sinistra a destra.
sequenza iniziale sequenza iniziale
(C,A,D,A,E,G,B,M,C)(C,A,D,A,E,G,B,M,C)sequenzasequenza ordinata ordinata (A,A,B,C,C,D,E,G,M)(A,A,B,C,C,D,E,G,M)
La sequenza ordinata contiene gli stessi elementi della sequenza iniziale e ogni elemento appare con la stessa molteplicità nelle due sequenze.
Una sequenza (aUna sequenza (a11,a,a22,…,a,…,an-1n-1,a,ann) è ordinata (sorted) se a) è ordinata (sorted) se a11 ≤ a ≤ a22 ≤ … ≤ ≤ … ≤
aan-1n-1 ≤a ≤ann
se e solo se il valore di ai è minore di quello di ai+1
oppure ai e ai+1 hanno lo stesso valore
55
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
A = Vettore ordinato A[i] ≤ A[j] con i, j=1, …,41, …,4 , i<j
Un vettore (array) rappresenta un insieme di elementi dello stesso tipo: gli elementi si distinguono uno dall’altro mediante un indice. L’insieme dei valori assumibili dagli indici di un’array dipende dal numero complessivo degli elementi dell’array (SIZE)
A =
Ordinamento di un vettoreOrdinamento di un vettore
Dato un vettore A di interi, ordinarlo in modo crescente (non-decrescente) significa trasformarlo in modo tale che, per ogni indice i, l’elemento A[i] sia minore o uguale di tutti gli altri elementi di indice j, con i<jEsempio:
A = Vettore iniziale
1100
22 1133
77
1100
22 1133
77
22 44 77 1133
11 22 33 44
66
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
““Un ordine perfetto è il fondamento di tutte le cose”Un ordine perfetto è il fondamento di tutte le cose”(Edmund Burke 1729-1797)(Edmund Burke 1729-1797)
L’accesso a collezioni di dati ordinate in modo opportuno è più semplice che non l’accesso a collezioni non ordinate.
A che servirebbe un elenco telefonico se gli utenti fossero elencati in ordine sparso?
Importanza dell’ordinamento (1)Importanza dell’ordinamento (1)
Anche nei calcolatori, è spesso utile gestire collezioni di dati ordinate secondo un qualche criterio di ordinamento, questo ad esempio permette di usare algoritmi di ricerca più efficienti (ricerca binaria)
77
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
procedure r_bin(in:n,elenco,chiave; out:trovato,indice)var elenco: array(1..n) of charactervar chiave: charactervar n,indice,mediano,primo,ultimo: integervar trovato: logicalbegin primo:= 1; ultimo:= n; trovato:= false repeat mediano := (primo+ultimo)/2 if chiave = elenco(mediano) then trovato := true else if chiave < elenco(mediano) then
ultimo := mediano - 1 else
primo := mediano + 1 endif endif until trovato or primo = ultimo indice := medianoend
procedure r_bin(in:n,elenco,chiave; out:trovato,indice)var elenco: array(1..n) of charactervar chiave: charactervar n,indice,mediano,primo,ultimo: integervar trovato: logicalbegin primo:= 1; ultimo:= n; trovato:= false repeat mediano := (primo+ultimo)/2 if chiave = elenco(mediano) then trovato := true else if chiave < elenco(mediano) then
ultimo := mediano - 1 else
primo := mediano + 1 endif endif until trovato or primo = ultimo indice := medianoend
Importanza dell’ordinamento (2)Importanza dell’ordinamento (2)La tecnica di ricerca binaria, rispetto alla ricerca esaustiva, consente di eliminare ad ogni passo metà degli elementi del vettore
chiave = 11
mediano=(9+1)/2=5; elenco[5]=19
22 55 1111 1515 1919 2828 3535 4141 5050
11<19 ---> primo =1; ultimo=4
mediano := (primo+ultimo)/2
primo=1; ultimo=9; trovato=false
primoprimo ultimoultimo
primo:= 1; ultimo:= n; trovato:= falseprimo:= 1; ultimo:= n; trovato:= false
mediano := (primo+ultimo)/2
if chiave < elenco(mediano) then ultimo := mediano - 1if chiave < elenco(mediano) then ultimo := mediano - 1
primoprimo ultimoultimo
primo=1; ultimo=4; trovato=falsemediano=(4+1)/2=2; elenco[2]=5
mediano := (primo+ultimo)/2mediano := (primo+ultimo)/2
55 19191919
11>5 ---> primo= 2+1=3
else primo := mediano + 1
55
else primo := mediano + 1
primo=3; ultimo=4; trovato=false
mediano=(3+4)/2=3; elenco[3]=11
Iterazione:1Iterazione:1Iterazione:2Iterazione:2Iterazione:3Iterazione:3
1111
if chiave = elenco(mediano) then trovato := trueif chiave = elenco(mediano) then trovato := true
Elemento è stato trovato nella terza locazione dell’array:
indice=3
indice := medianoindice := mediano
trovato = true
88
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
type studente : record cognome: character
nome : character matricola : integer
media : integerend
var stud1,stud2,stud3,stud4,stud5: studente
type studente : record cognome: character
nome : character matricola : integer
media : integerend
var stud1,stud2,stud3,stud4,stud5: studente
Il valore su cui si effettua l’ordinamento di un insieme di elementi si definisce chiave (key) di ordinamento. Nel caso si desideri ordinare insiemi di variabili con differenti tipi di valori (record o strutture) occorre definire bene la chiave dell’ordinamento.
Chiave di ordinamentoChiave di ordinamento
Esempio: Ordinamento per cognome e Ordinamento per cognome e nome (Es. ordinamento nome (Es. ordinamento alfabetico del registro di alfabetico del registro di classe) classe)
Ordinamento per Ordinamento per media (con valori media (con valori ripetuti)ripetuti)
99
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
KeyKey11
Verdi Bianchi Russo BianchiEsposit
oNeri
KeyKey22
Mario Antonio Carlo Gianni Luca Marco
KeyKey33 00130 00134 00120 00127 00140 00124
KeyKey44
6 9 6 8 5 7
11 22 33 44 55 66
Problema:Problema: ordinare in ordine crescente un insieme di studenti considerando le chiavi di ordinamento:
Key1=Key1=cognome;cognome; Key2=Key2=nome;nome; Key3=Key3=matricola; matricola; Key4=Key4=media media
scolastica;scolastica;
KeyKey11
Russo Neri Bianchi Verdi Bianchi Esposito
KeyKey22
Carlo Marco Gianni Mario Antonio Luca
KeyKey33 0012000120 0012400124 0012700127 0013000130 0013400134 0014000140
KeyKey44
6 7 8 6 9 5
Ordinamento crescente per matricolaOrdinamento crescente per matricola
11 22 33 44 55 66
1010
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Ordinamento crescente per media scolasticaOrdinamento crescente per media scolastica Key1Key1 Esposito Verdi Russo Neri Bianchi Bianchi
Key2Key2 Luca Mario Carlo Marco Gianni Antonio
Key3Key3 00140 00130 00120 00124 00127 00134
KeyKey44
55 66 66 77 88 9911 22 33 44 55 66
Key1Key1 Verdi Bianchi Russo Bianchi Esposito Neri
Key2Key2 Mario Antonio Carlo Gianni Luca Marco
Key3Key3 00130 00134 00120 00127 00140 00124
Key4Key4 6 9 6 8 5 7
11 22 33 44 55 66
KeyKey11
BianchiBianchi BianchiBianchi EspositoEsposito NeriNeri RussoRusso VerdiVerdi
KeyKey22
AntonioAntonio GianniGianni LucaLuca MarcoMarco CarloCarlo MarioMario
Key3Key3 00134 00127 00140 00124 00120 00130
Key4Key4 9 8 5 7 6 6
Ordinamento crescente per cognome e nomeOrdinamento crescente per cognome e nome
11 22 33 44 55 66
1111
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Iterazione e ricorsione (1)Iterazione e ricorsione (1)
Gli algoritmi di ordinamento possono essere iterativi e ricorsivi
Iterazione: ripetere piu’ volte una sequenza di operazioni
Esempio: somma i primi n interi: ( ( ( ( ( ( (1)(1) + 2)+ 2) +3)+3)+…+…++ n)n)
for (i=1, i<=n, i++) somma=somma +i
La caratteristica fondamentale di un algoritmo ITERATIVO è che a ogni passo è disponibile un risultato parziale: dopo k passi, si ha a disposizione il risultato parziale relativo al caso k
1212
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Gli algoritmi ricorsivi si basano sulla possibilità di definire una funzione in termini di se stessa.
Una funzione è definita ricorsivamente quando nella sua definizione compare un riferimento a se stessa.
Iterazione e ricorsione (2)Iterazione e ricorsione (2)
Esempio: somma i primi n iteri
SSnn= n + S= n + Sn-1 n-1 == nn ++ somma dei primi ((n-1n-1)) numeri interi
Risolvere un problema con un approccio ricorsivo comporta
• di identificare un “caso base” la cui soluzione sia nota
• di riuscire a esprimere la soluzione al caso generico n in termini dello stesso problema in uno o più casi più semplici (n-1, n-2, etc).
1313
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Esempio di funzione ricorsiva: Esempio di funzione ricorsiva:
“somma dei primi (n-1) interi” è una istanza più semplice del problema “somma dei primi n interi” e tale istanza può essere scomposta, a sua volta, in un’istanza ancora più semplice
SSnn= n + S= n + Sn-1n-1 somma dei primi somma dei primi nn iteri iteri
n + n + soluzione del problema della somma dei primi (soluzione del problema della somma dei primi (n-1n-1) iteri) iteri
Osserviamo che nella ricorsione, a differenza dell’iterazione, non si dispone di un risultato parziale finché non si è giunti fino all’istanza elementare
SSnn= n+(n-1)+S= n+(n-1)+Sn-2n-2
Procedendo in queste scomposizioni si giunge fino all’istanza banale del problema SS11= 1= 1
SSnn= n+(n-1)+(n-2)+(n-3)+…+1= n+(n-1)+(n-2)+(n-3)+…+1
1414
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Selection-sort (ordinamento per Selection-sort (ordinamento per selezione)selezione)
Sia A un array di n elementi da ordinare. L’ algoritmo selection-sort seleziona l’elemento con valore minore e lo scambia con il primo elemento. Tra gli n-1 elementi rimasti viene poi ricercato quello con valore minore e scambiato con il secondo e così di seguito fino all’ultimo elemento.
METODO: Iteriamo i seguenti passi:
•l’array A è diviso in 2 parti Parte iniziale ordinataParte iniziale ordinata | parte da ordinare| parte da ordinare
•cerchiamo l’elemento minimo nella parte non ordinata e lo scambiamo con il primo della parte non ordinata
1515
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Per i=n-1Per i=n-1:: A[1..n-2] | A[n-1],A[n]cerca il minimo tra A[n-1] e A[n], scambialo con A[n-1] ARRAY ARRAY A ORDINATO!A ORDINATO!
Parte iniziale ordinataParte iniziale ordinata | parte da ordinare| parte da ordinare
Selection-sort Selection-sort
I iterazioneI iterazione:: A[1..n] non ordinato, cerca minimo di A[1..n] e scambialo con A[1]. Quindi: A[1] | A[2..n]
II iterazioneII iterazione:: A[1] ordinato, A[2..n] non ordinato, cerca minimo di A[2..n] e scambialo con A[2]. Quindi: A[1]A[2] | A[3..n]
generica iterazionegenerica iterazione:: A[1..i-1] ordinato, A[i..n] non ordinato, cerca minimo di A[i..n] e scambialo con A[i]. Quindi: A[1..i-1] A[i]| A[i+1,..n]
1616
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
SelectionSort(A, min, temp) for i=1 to n-1 do min := i for j=i+1 to n do
If A(min)>A(j) then min := jendif
endfor temp = A[min] A[min] = A[i] A[i] = temp endfor
SelectionSort(A, min, temp) for i=1 to n-1 do min := i for j=i+1 to n do
If A(min)>A(j) then min := jendif
endfor temp = A[min] A[min] = A[i] A[i] = temp endfor
1515
Esempio selection-sort:Esempio selection-sort: Sia A un array di 6 elementi da ordinare in modo crescente
11
1111 55 11 1515 77 771111 11 min := imin := i
j=2j=2
min=1min=1min=2min=2
1111 55
for j=i+1 to n do If A(min)>A(j) then min := jendif
for j=i+1 to n do If A(min)>A(j) then min := jendif
j=3j=3
55
min=3min=3
j=4j=4 j=6j=6j=5j=5
temp = A[min] A[min] = A[i] A[i] = temp
temp = A[min] A[min] = A[i] A[i] = temp
1111 11 i=1i=1 i=2i=2 min := i
min=2min=2
min := i
for j=i+1 to n do If A(min)>A(j) then min := jendif
j=3j=3 j=4j=4 j=5j=5 j=6j=6
for j=i+1 to n do If A(min)>A(j) then min := jendif
temp = A[min] A[min] = A[i] A[i] = temp
55
55 i=3i=3
temp = A[min] A[min] = A[i] A[i] = temp
min := i
min=3min=3
min := i
for j=i+1 to n do If A(min)>A(j) then min := jendif
j=4j=4 j=5j=5
1111 77
La parte sinistra La parte sinistra del vettore è già del vettore è già ordinataordinata
min=5min=5
77
j=6j=6
for j=i+1 to n do If A(min)>A(j) then min := jendif
temp = A[min] A[min] = A[i] A[i] = temp
temp = A[min] A[min] = A[i] A[i] = temp
min := i i=4i=4
min=4min=4
min := i
for j=i+1 to n do If A(min)>A(j) then min := jendif
min=5min=5
j=6j=6
for j=i+1 to n do If A(min)>A(j) then min := jendif
temp = A[min] A[min] = A[i] A[i] = temp
1111temptemp
1111 1515
j=5j=5
temp = A[min] A[min] = A[i] A[i] = temp
min := i i=5i=5 min := i
for j=i+1 to n do If A(min)>A(j) then min := jendif
for j=i+1 to n do If A(min)>A(j) then min := jendif
temp = A[min] A[min] = A[i] A[i] = temp
1515
1515 19191919
temp = A[min] A[min] = A[i] A[i] = temp
1717
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
procedure ord_sel_max(in:n; inout:a)var n,indice_max:integervar a:array(1..n)of characterbeginfor i=n,2 step=-1 do indice_max := 1 for k=2,i do
if a(indice_max)<a(k)then
indice_max := kendif
endfor scambiare_c(a(i),a(indice_max)) endforend
procedure ord_sel_max(in:n; inout:a)var n,indice_max:integervar a:array(1..n)of characterbeginfor i=n,2 step=-1 do indice_max := 1 for k=2,i do
if a(indice_max)<a(k)then
indice_max := kendif
endfor scambiare_c(a(i),a(indice_max)) endforend
Problema:Problema:
Sviluppare un algoritmo di selection sort basato sulla selezione del massimo per ordinare in modo crescente un array A di n elementi
for i=n,2 step=-1 do determinare l’elemento massimo della porzione 1..i dell’array metterlo all’ultimo posto della porzioneendfor
1818
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
L’operazione dominante per il selection-sort è il confronto tra
coppie di elementi, per n-1 volte bisogna determinare il minimo
tra gli elementi non ordinati e se necessario effettuare uno
scambio:
Durante la prima iterazione bisogna effettuare n-1 confronti per
determinare il minimo tra gli n elementi.
Durante la seconda iterazione bisogna effettuare n-2 confronti
per determinare il minimo tra gli n-1 elementi.
….
Analisi del selection-sort (1)Analisi del selection-sort (1)
1919
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Quindi il numero di confronti è : n-i = (n-1)+(n-2)+…+2+1 n-i = (n-1)+(n-2)+…+2+1
= n(n-1)/2= n(n-1)/2
Per cui il tempo di esecuzione dell’algoritmo tende a n2
Il comportamento del selection-sort è indipendente dall’ordine preesistente nell’array da ordinare: il caso peggiore (array ordinato in ordine decrescente) e quello migliore coincidono (array ordinato in ordine crescente)
i=1i=1
n-1n-1
Analisi del selection-sort (2)Analisi del selection-sort (2)
Durante la n-1 iterazione bisogna effettuare 1 confronti per determinare il minimo tra 2 elementi.
2020
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Insertion-sort (ordinamento per Insertion-sort (ordinamento per inserimento)inserimento)
L’insertion-sort è un algoritmo molto semplice che si basa sul metodo usato per ordinare le carte da gioco: “per ordinare le carte nelle tue mani estrai una carta, scala le carte rimanenti, e inserisci la carta estratta nel posto corretto tra quelle già considerate e ordinate”
Analogamente per ordinare un vettore di interi a[1…n] in ordine crescente, consideriamo il primo elemento come un sottovettore ordinato e inseriamo gli elementi a[2],…,a[n] uno dopo l’altro nella giusta posizione tra quelli già considerati e ordinati
2121
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Metodo Insertion-sort:Metodo Insertion-sort:
• ordinare i primi 2 elementi (porzione 1..2);
•ordinare i primi 3 elementi (porzione 1..3), inserendo il terzo elemento nella posizione corretta rispetto ai precedenti;
•ordinare i primi 4 elementi (porzione 1..4), inserendo il quarto elemento nella posizione corretta rispetto ai precedenti;
•……
•ordinare i gli n elementi (porzione 1..n),inserendo l’ennesimo elemento nella posizione corretta rispetto ai precedenti
2222
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
InsertionSort(A,n, temp) for i=2 to n do temp := a(i) j := i-1 while j>=1 and temp<a(j)
a(j+1) := a(j) j := j-1
end while a(j+1) := temp endfor end
InsertionSort(A,n, temp) for i=2 to n do temp := a(i) j := i-1 while j>=1 and temp<a(j)
a(j+1) := a(j) j := j-1
end while a(j+1) := temp endfor end
AA 15151111 55 11 1515 77 55 1111 1919
Esempio: Sia A il vettore da ordinare.Esempio: Sia A il vettore da ordinare.
Ordiniamo i primi 2 elementi (porzione 1-2); poi ordiniamo gli elementi dalla terza posizione in poi inserendoli nella posizione corretta rispetto ai precedenti
temptemp
55
j=1j=1
i=2i=2
i=2i=2 temp := a(i) j := i-1 temp := a(i) j := i-1
a(j+1) := a(j) j := j-1
j=0j=0
a(j+1) := a(j) j := j-1
a(j+1) := temp a(j+1) := temp
i=3i=3
i=3i=3
j=2j=2
temp := a(i) j := i-1
11
temp := a(i) j := i-1
a(j+1) := a(j) j := j-1
1111 1111 1111 55
j=1j=1
55
j=0j=0
a(j+1) := a(j) j := j-1
a(j+1) := temp
11
a(j+1) := temp
temp := a(i) j := i-1
i=4i=4
i=4i=4
j=3j=3
1515
temp := a(i) j := i-1
La condizione è falsa
a(j+1) := temp
i=5i=5 temp := a(i) j := i-1
a(j+1) := temp
i=5i=5
j=4j=4
77
a(j+1) := a(j) j := j-1
temp := a(i) j := i-1
1515
j=3j=3
1111
j=2j=2
La condizione è falsa
a(j+1) := a(j) j := j-1
a(j+1) := temp
77
La condizione è falsa
a(j+1) := temp
i=6i=6
i=6i=6
j=5j=5
1919
temp := a(i) j := i-1 temp := a(i) j := i-1
La condizione è falsa
a(j+1) := temp
1919
a(j+1) := temp
endforendfor
L’insertion-sort è un algoritmo di ordinamento stabile
2323
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Il metodo di ordinamento ad inserzione si basa sull'idea che un vettore ordinato si ottiene inserendo le sue componenti una per una "al posto giusto".
Non si introduce un secondo vettore, ma si "simula" l‘inserzione degli elementi nel vettore dato (ordinamento in loco).
L’insertion-sort è un algoritmo stabile
2424
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Algoritmi di ordinamento stabiliAlgoritmi di ordinamento stabiliSe nell’array da ordinare ci sono due o più elementi con lo stesso valore, allora tali elementi compaiono nell’array di output nello stesso ordine in cui compaiono in quello di input. (Algoritmo Stabile)
voto Carlo voto Rita voto Mariovoto Luca voto Paolo voto Gina
5 5 6 7 7 8
765875 765875
voto Carlo
a[1]
voto Luca
a[2]
voto Gina
a[3]
voto Mario
a[5]
voto Rita
a[4]
voto Paolo
a[6]
Esempio (Alg. Stabile) : ordinare un vettore di voti scolastici
Si conserva l’ordinamento sul nome!
2525
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
5 7 8 5 6 7
voto Carlo
a[1]voto Luca
a[2]
voto Gina
a[3]
voto Mario
a[5]
voto Rita
a[4]
voto Paolo
a[6]
voto Carlo
voto Luca voto Gina
5 7 8
Problema:Problema:
Verificare che l’algoritmo di selection sort basato sulla selezione del massimo per ordinare in modo crescente un array A di n elementi non è stabile
i=6i=6 i=5i=5
7
voto Paolo
6
voto Mario
i=4i=47
voto Paolo
5
voto Rita
i=3i=36
voto Mario
voto Rita
5
i=2i=25
voto Rita
765875 765875voto Carlo voto Luca voto Gina voto Mariovoto Rita voto Paolo
Si perde l’ordinamento sul nome: algoritmo non-stabileSi perde l’ordinamento sul nome: algoritmo non-stabile
for i=n,2 step=-1 dodeterminare l’elemento massimo della porzione 1..i dell’array metterlo all’ultimo posto della porzioneendfor
for i=n,2 step=-1 dodeterminare l’elemento massimo della porzione 1..i dell’array metterlo all’ultimo posto della porzioneendfor
2626
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
L’operazione dominante per l’algoritmo è il confronto tra coppie di elementi. L'ordinamento per inserimento inserisce gli elementi lavorando meno se essi sono gia' parzialmente ordinati.
Analisi delle prestazioni dell’insertion-Analisi delle prestazioni dell’insertion-sort (1) sort (1)
Il caso migliore si ha quando il vettore è già ordinato in modo crescente in tal caso bastano n-1 confronti.
Il caso peggiore si ottiene invece nel caso in cui la sequenza di elementi si presenta in ordine inverso, cioè quando l’array è ordinato in modo decrescente, perchè in questo caso il numero di confronti sarà pari al numero di elementi già ordinati.
2727
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Quindi il numero di confronti totali su di un array di dimensione n è:
i = 1 + 2 + 3 + ... + n-1 = n(n-1)/2i = 1 + 2 + 3 + ... + n-1 = n(n-1)/2
Analizziamo il caso peggiore considerando l’ordinamento delle carte da gioco:
i=1i=1
n-1n-1
Analisi delle prestazioni dell’insertion-Analisi delle prestazioni dell’insertion-sort(2) sort(2)
l’insertion-sort durante la prima passata esegue un confronto con con la carta più a sinistra nell’array
durante la seconda passata esegue due confronti con le due carte più a sinistra dell’array);
durante la n-1 esima passata vengono eseguiti al più n-1 confronti
2828
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Bubble-sort (ordinamento a bolle)Bubble-sort (ordinamento a bolle)
L’ordinamento a bolle è un algoritmo semplice basato sul metodo degli scambi.Si fanno “salire” gli elementi più piccoli verso l’inizio del vettore scambiandoli con quelli adiacenti.
Si procede confrontando gli elementi a coppie e ogni qualvolta si trova una coppia non ordinata si scambiano di posto i due elementi.
Dato il vettore A[n], si opera confrontando A[1] con A[2] e se A[1] è maggiore di A[2], si effettua uno scambio tra i due; vengono poi confrontati A[2] con A[3], A[3] con A[4], …A[n-1] con A[n] scambiando di posto quegli elementi che non formano coppie ordinate.
2929
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Alla fine dell’esecuzione del primo ciclo di operazioni l’elemento più grande si trova automaticamente in ultima posizione in quanto gli elementi più piccoli sono "risaliti" nel vettore come delle bolle (da qui la definizione di Bubble-Sort).
Bubble-sort (ordinamento a bolle)Bubble-sort (ordinamento a bolle)
Successivamente, al termine del secondo ciclo di operazioni, l’elemento maggiore tra A[1], A[2],….A[n-1] sarà posizionato alla penultima (n-1) posizione; si procede in questo modo finchè non ci saranno più valori da scambiare (array ordinato)
3030
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
BubbleSort(A,n,scambio,t
emp)
i:=1
repeat
scambio:= 0
for j=i+1 to n do
if (A[j] < A[j-1])
then temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
endif
endfor
until scambio=0
end
BubbleSort(A,n,scambio,t
emp)
i:=1
repeat
scambio:= 0
for j=i+1 to n do
if (A[j] < A[j-1])
then temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
endif
endfor
until scambio=0
end
Esempio:Esempio: Sia A il vettore da ordinare
AA 15151111 55 11 1515 77 1919
temptemp
55
55 1111
j-1=1j-1=1
j=3j=3
1111
j=2j=2
77
ScambioScambio=0=0
scambio:= 0scambio:= 0
temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
ScambioScambio=1=1
j-1=2j-1=2
temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
11
55 1111 11temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
1111 11
j=4j=4
j-1=3j-1=3
j=5j=5
j-1=4j-1=4
Il bubble-sort è un algoritmo stabile come l’insertion-sort
temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
77
1515 1515 77temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
11
55 11
j=2j=2
j-1=1j-1=1
j=4j=4
j-1=3j-1=3
1111 77
77
Scambio=0 Scambio=0
Vettore Ordinato!Vettore Ordinato!
19191515temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
scambio:=1
La condizione è falsa
3131
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Nel bubble sort l’operazione dominante è il confronto tra coppie di elementi, l’operazione di scambio degli elementi viene eseguita meno spesso rispetto al confronto degli elementi e ha lo stesso costo.
Analisi delle prestazioni del bubble-Analisi delle prestazioni del bubble-sort(1)sort(1)
L’algoritmo BubbleSort esegue un numero di operazioni variabili a seconda dell’ordinamento già presente nel vettore
Il caso migliore si ha quando l’array è già ordinato ed è sufficiente effettuare solo un ciclo per verificare che tutti gli elementi sono ordinati, quindi sono sufficienti n-1 confronti.
Il caso peggiore si ha quando gli elementi nell’array sono ordinati in senso decrescente.
3232
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Quindi nel caso peggiore il numero di confronti e scambi su di un array di dimensione n è:
(n-i) = n(n-i) = n 1 - 1 - i = n(n-1)-n(n-1)/2 = n(n-1)/2i = n(n-1)-n(n-1)/2 = n(n-1)/2
Nel caso peggiore il bubble sort effettua i seguenti confronti:
i=1i=1
n=1n=1 n=1n=1 n=1n=1
i=1i=1 i=1i=1
Analisi delle prestazioni del bubble-Analisi delle prestazioni del bubble-sort(1)sort(1)
Durante il primo ciclo vengono eseguiti n-1 confronti e altrettanti scambi
Durante il secondo ciclo vengono eseguiti n-2 confronti e altrettanti scambi
Durante il terzo ciclo vengono eseguiti n-3 confronti e altrettanti scambi
….
Durante l’n-esimo ciclo viene eseguito un confronto e uno scambio
3333
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
““DIVIDE ET IMPERA”DIVIDE ET IMPERA”dicevano i latini: sia con il significato che una volta conquistato un nuovo territorio è meglio tenere diviso il popolo, se è ostile, per evitare rivolte e sovversioni; sia con il significato di partizionare il territorio per amministrarlo meglio.
Algoritmi di ordinamento ricorsivi Algoritmi di ordinamento ricorsivi
Il motto latino ‘Divide et Impera’ è stato acquisito dall’informatica come tecnica per risolvere problemi complessi, in pratica si genera una sequenza di istanze via via più semplici del problema, fino all'istanza che non è più suddivisibile e che ha soluzione banale
3434
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Gli algoritmi di ordinamento visti finora possono essere realizzati anche con metodi ricorsivi. La ricorsione è un metodo molto più elegante dell’iterazione
Selection-Sort ricorsivoSelection-Sort ricorsivo
La versione ricorsiva del Selection-Sort si basa su di un idea molto semplice:
ordina il vettore = metti il minimo all'inizio + ordina il resto del ordina il vettore = metti il minimo all'inizio + ordina il resto del vettore vettore
Alla prima invocazione bisogna ordinare tutto il vettore, alla seconda tutto tranne il primo, poi tutto tranne il secondo, ecc.
Useremo un parametro ‘inizio’ per ordinare il vettore a partire dall'indice ‘inizio’ fino alla fine, ordinando la parte di vettore:
A[inizio], A[inizio+1], ... , A[A.length-1]
3535
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Metodo ricorsivo Selection-Sort:
Metto il minimo in prima posizione, poi ordino quello che resta del vettore.
Algoritmo ricorsivo del Selection-SortAlgoritmo ricorsivo del Selection-Sort
Cerco il minimo fra A[inizio], A[inizio+1], ... , A[A.length-1]
Lo metto in A[inizio] (faccio lo scambio)
Faccio la chiamata ricorsiva passando inizio+1
Manca ancora il caso base della ricorsione!
SelectRic(int A[], int inizio)
{
int i, minpos;
minpos=inizio;
for(i=inizio; i<A.length;
i++)
{
if(A[i]<A[minpos])
minpos=i;
int temp=A[inizio];
A[inizio]=A[minpos];
A[minpos]=temp;
}
SelectRic(A, inizio+1);
}
SelectRic(int A[], int inizio)
{
int i, minpos;
minpos=inizio;
for(i=inizio; i<A.length;
i++)
{
if(A[i]<A[minpos])
minpos=i;
int temp=A[inizio];
A[inizio]=A[minpos];
A[minpos]=temp;
}
SelectRic(A, inizio+1);
}
3636
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Selection-Sort caso base:Selection-Sort caso base:
Ogni volta che viene richiamata la funzione SelectRic (invocazione del metodo), la parte di vettore da ordinare ha un elemento in meno. Alla fine si arriva al vettore di un elemento, questo succede quando inizio è l'ultimo elemento del vettore.
In pratica: inizio aumenta di uno a ogni invocazione ricorsiva e quando arriva alla fine si deve ordinare la parte di vettore con un elemento solo (che è già banalmente ordinato!)
SelectRic(int A[], int
inizio)
{
int i, minpos;
if(inizio>=A.length-1)
return;
minpos=inizio;
for(i=inizio; i<A.length;
i++)
if(A[i]<A[minpos])
minpos=i;
int temp=A[inizio];
A[inizio]=A[minpos];
A[minpos]=temp;
SelectRic(A, inizio+1);
}
SelectRic(int A[], int
inizio)
{
int i, minpos;
if(inizio>=A.length-1)
return;
minpos=inizio;
for(i=inizio; i<A.length;
i++)
if(A[i]<A[minpos])
minpos=i;
int temp=A[inizio];
A[inizio]=A[minpos];
A[minpos]=temp;
SelectRic(A, inizio+1);
}
3737
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Nell’ordinamento a bolle dobbiamo far risalire gli elementi più leggeri (più piccoli) fino alla cima del vettore.
Bubble-Sort ricorsivoBubble-Sort ricorsivo
Il ciclo for mette il massimo alla fine, dopo aver fatto questo, resta da ordinare il resto del vettore (tutto tranne l'ultimo elemento). Nella chiamata ricorsiva viene specificato dove il vettore termina (cioè dove finisce la parte di vettore da ordinare) Faccio il ciclo di confronti, che
mette il massimo alla fine.
Faccio l’ invocazione ricorsiva su tutto il vettore tranne l’ultimo elemento.
Manca il caso base!
BubbleRic(int A[], int
fine) {
int i, temp;
for(i=0; i<=fine-1; i+
+) if(A[i]>A[i+1])
{ temp=A[i];
A[i]=A[i+1];
A[i+1]=temp;
}
BubbleRic(A, fine-1);
}
BubbleRic(int A[], int
fine) {
int i, temp;
for(i=0; i<=fine-1; i+
+) if(A[i]>A[i+1])
{ temp=A[i];
A[i]=A[i+1];
A[i+1]=temp;
}
BubbleRic(A, fine-1);
}
3838
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Bubble-Sort: caso baseBubble-Sort: caso base
La parte di vettore da ordinare diventa sempre più piccola a ogni invocazione ricorsiva.
Alla prima invocazione fine vale A.length-1 poi diminusce di uno, poi ancora di uno, ecc.
Quando fine==0 la parte di vettore da ordinare è il solo primo elemento (che è già ordinato!)
BubbleRic(A[], fine) {
int i, temp;
if(fine==0) return; // CASO // CASO
BASEBASE
for(i=0; i<=fine-1; i++)
if(A[i]>A[i+1]) {
temp=A[i];
A[i]=A[i+1];
A[i+1]=temp;
}
BubbleRic(A, fine-1);
}
BubbleRic(A[], fine) {
int i, temp;
if(fine==0) return; // CASO // CASO
BASEBASE
for(i=0; i<=fine-1; i++)
if(A[i]>A[i+1]) {
temp=A[i];
A[i]=A[i+1];
A[i+1]=temp;
}
BubbleRic(A, fine-1);
}
3939
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Insertion-Sort ricorsivoInsertion-Sort ricorsivo
L’idea di ordinamento è simile al modo che, durante una partita a carte, si usa per ordinare le carte nella propria mano.
Si inizia con la mano vuota e le carte capovolte sul tavolo
Poi si prende una carta alla volta dal tavolo e si inserisce nella giusta posizione
Per trovare la giusta posizione per una carta, la confrontiamo con le altre carte nella mano, da destra verso sinistra. Ogni carta più grande verrà spostata verso destra in modo da fare posto alla carta da inserire.
L’insertion-Sort è uno algoritmo di ordinamento molto efficiente per ordinare un piccolo numero di elementi
4040
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
INSERTION SORT RICORSIVO INSERTION SORT RICORSIVO
start from = 1
insertion_sort( A, from, to)
{
if ( from+1 > to ) { // CASO BASE from > to il vettore è ordinato
temp = A[from+1]);
i = from;
while ( i>0 AND A[i] > temp) { // passo base
A[i+1]=A[i]; i=i-1;
}
A[i+1] = temp;
insertion_sort( A , from+1, to) // RICORSIONE
}
}
INSERTION SORT RICORSIVO INSERTION SORT RICORSIVO
start from = 1
insertion_sort( A, from, to)
{
if ( from+1 > to ) { // CASO BASE from > to il vettore è ordinato
temp = A[from+1]);
i = from;
while ( i>0 AND A[i] > temp) { // passo base
A[i+1]=A[i]; i=i-1;
}
A[i+1] = temp;
insertion_sort( A , from+1, to) // RICORSIONE
}
}
4141
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Un altro modo per confrontare le prestazioni degli algoritmi di ordinamento consiste, semplicemente, nell’eseguire molti test per ogni algoritmo al crescere della dimensione n dell’input e nel confrontarne i tempi di esecuzione misurati tenendo conto dei casi in cui il vettore è ordinato in modo crescente, decrescente e random. I tempi sono generalmente espressi nella forma minuti secondi.
Questo tipo di misurazione ha lo svantaggio che i tempi di esecuzione degli algoritmi dipendono dalle prestazioni della macchina su cui sono eseguiti (velocità del processore, capacità della memoria centrale), per cui il tempo di esecuzione di un algoritmo può variare notevolemente se eseguito su macchine differenti.
Questo tipo di misurazione ha lo svantaggio che i tempi di esecuzione degli algoritmi dipendono dalle prestazioni della macchina su cui sono eseguiti (velocità del processore, capacità della memoria centrale), per cui il tempo di esecuzione di un algoritmo può variare notevolemente se eseguito su macchine differenti.
Prestazioni degli algoritmi di Prestazioni degli algoritmi di ordinamento ordinamento (risultati sperimentali)(risultati sperimentali)
4242
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Questi sono i risultati forniti da un programma (eseguito su un Pentium 3 di 500 MegaHertz) utilizzato per ordinare con gli algoritmi analizzati in questo corso un vettore di 15.000 elementi. I tempi sono nella forma minuti secondi.
4343
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
Implementazione degli algoritmi di Implementazione degli algoritmi di sortingsorting
Gli algoritmi di sorting si possono implementare in svariati modi (Java, linguaggio C, Visual Basic, MATLAB, etc.) in questo corso abbiamo scelto il metodo più semplice, cioè le macro di Excel. Questa scelta è mirata a motivare l’interesse di tutti gli alunni, compresi quelli che potrebbero ritenere ‘difficile’ l’uso di metodi più sofisticati.
Analizziamo delle semplici simulazioni degli algoritmi di sorting che sono state sviluppate con le macro di Microsoft Excel
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
BubbleSort 3-D (curiosità)BubbleSort 3-D (curiosità)
Al seguente link è disponibile un algoritmo 3-D per ordinare pixel di colori con il Bubble sort
http://www.magma.ca/~gtaylor/3dBubbleSort.htm
Eseguibile BubbleSort 3-D3-D
ALGORITMI DI ORDINAMENTOALGORITMI DI ORDINAMENTO
RiferimentiRiferimenti
http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html
http://faculty.harker.org/robbc/Pages/Software/TheSorter/TheSorter.htm
http://www.magma.ca/~gtaylor/3dBubbleSort.htm
http://math.hws.edu/TMCM/java/xSortLab/
http://www.geocities.com/SiliconValley/Network/1854/Sort1.html