Didattica della programmazione I
Prof. Giulio Giunta
Algoritmi di ordinamento
Calzetta Emilia
Cervone Vincenzo
ALGORITMI DI ORDINAMENTO
Contenuti:
Algoritmi di ordinamento iterativi e ricorsivi
Ordinamento per inserimento: Insertion-sort
Ordinamento per selezione del min/max: Selection-sort
Ordinamento a bolle: Bubble-sort
Analisi della complessità nel contare gli scambi e i confronti (caso peggiore)
Analisi comparata
Simulazioni in linguaggio VB
Riferimenti:
Cormen, Leiserson, Rivest- Introduzione agli algoritmi -McGrawHill
ALGORITMI DI ORDINAMENTO
Classe: 3^ I.T.I.S.
Prerequisiti:
Conoscenze sull’organizzazione dei dati mediante la struttura vettoriale
Conoscenze della teoria della ricorsione e dell’iterazione
Conoscenze della teoria e implementazione degli algoritmi
Conoscenze del linguaggio Visual Basic e delle Macro di Excel
Obiettivi:
Saper gestire l’organizzazione e ordinamento dei dati in un vettore
Capire l’importanza dell’ordinamento dei dati
Utilizzare le strutture di iterazione e ricorsione
Analizzare le applicazioni relative agli argomenti teorici affrontati
Modalità di lavoro:
lezioni frontali
utilizzo del laboratorio
ALGORITMI DI ORDINAMENTO
Ordinamento di una sequenza
Una 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
(C,A,D,A,E,G,B,M,C)
sequenza ordinata (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 (a1,a2,…,an-1,an) è ordinata (sorted) se a1 ≤ a2 ≤ … ≤ an-1 ≤an
se e solo se il valore di ai è minore di quello di ai+1
oppure ai e ai+1 hanno lo stesso valore
4
ALGORITMI DI ORDINAMENTO
Ordinamento di un vettore
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 = 10 2 13 7
1
2
3
4
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<j
Esempio:
A = 10
2
13
7
Vettore iniziale
2
4
7
13
Vettore ordinato
A=
A[i] ≤ A[j] con i, j=1, …,4 , i<j
5
ALGORITMI DI ORDINAMENTO
Importanza dell’ordinamento (1)
“Un ordine perfetto è il fondamento di tutte le cose”
(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?
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)
6
ALGORITMI DI ORDINAMENTO
Importanza dell’ordinamento (2)
La tecnica di ricerca binaria, rispetto alla ricerca esaustiva, consente di
eliminare ad ogni passo metà degli elementi del vettore
2
5
11
primo
15 19 28 35 41 50
ultimo
chiave = 11
primo=1; ultimo=9; trovato=false
primo=3;
trovato
ultimo=4;
= true
trovato=false
primo=1;
ultimo=4;
trovato=false
mediano=(9+1)/2=5;
mediano=(4+1)/2=2;
elenco[5]=19
mediano=(3+4)/2=3;
elenco[2]=5
elenco[3]=11
11<19 ---> primo =1; ultimo=4
11>5 ---> primo= 2+1=3
Elemento è stato trovato nella terza
locazione dell’array: indice=3
Iterazione:2
Iterazione:3
Iterazione:1
ultimo
procedure r_bin(in:n,elenco,chiave;
out:trovato,indice)
var elenco: array(1..n) of character
var chiave: character
var n,indice,mediano,primo,ultimo:
integer
var trovato: logical
begin
primo:=
primo:=1;
1;ultimo:=
ultimo:=n;
n;trovato:=
trovato:=false
false
repeat
mediano
mediano
:=
:=
(primo+ultimo)/2
(primo+ultimo)/2
mediano
:=
(primo+ultimo)/2
chiave == elenco(mediano)
elenco(mediano) then
then
ifif chiave
trovato :=
:= true
true
trovato
else
ififchiave
chiave<<elenco(mediano)
elenco(mediano)then
then
ultimo
ultimo:=:=mediano
mediano- -11
else
primo :=
:= mediano
mediano ++ 11
primo
endif
endif
until trovato or primo = ultimo
indice
indice :=
:= mediano
mediano
end
7
ALGORITMI DI ORDINAMENTO
Chiave di ordinamento
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.
Esempio:
Ordinamento per cognome e nome
(Es. ordinamento alfabetico del
registro di classe)
Ordinamento per media
(con valori ripetuti)
type studente : record
cognome: character
nome : character
matricola : integer
media : integer
end
var stud1,stud2,stud3,stud4,stud5: studente
8
ALGORITMI DI ORDINAMENTO
Problema: ordinare in ordine crescente un insieme di studenti considerando
le chiavi di ordinamento:
Key1=cognome; Key2=nome; Key3=matricola; Key4=media scolastica;
Key1
Verdi
Bianchi
Russo
Key2
Key3
Mario
00130
Antonio
00134
Carlo
00120
Key4
6
9
1
2
Neri
Bianchi
Gianni
Esposito
Luca
00127
00140
6
8
5
00124
7
3
4
5
6
Marco
Ordinamento crescente per matricola
Key1
Russo
Neri
Verdi
Mario
Bianchi
Antonio
Esposito
Marco
Bianchi
Gianni
Key2
Carlo
Key3
00120
00124
00127
00130
00134
00140
Key4
6
7
8
6
9
5
1
2
3
4
5
6
Luca
9
ALGORITMI DI ORDINAMENTO
Key1
Verdi
Bianchi
Russo
Bianchi
Esposito
Neri
Key2
Mario
Antonio
Carlo
Gianni
Luca
Marco
Key3
00130
00134
00120
00127
00140
00124
Key4
6
9
6
8
5
7
1
2
3
4
5
6
Ordinamento crescente per media scolastica
Key1
Esposito
Verdi
Russo
Neri
Bianchi
Bianchi
Key2
Luca
Mario
Carlo
Marco
Gianni
Antonio
Key3
00140
00130
00120
00124
00127
00134
Key4
5
6
6
7
8
9
1
2
3
4
5
6
Ordinamento crescente per cognome e nome
Key1
Bianchi
Bianchi
Esposito
Neri
Russo
Verdi
Key2
Antonio
Gianni
Luca
Marco
Carlo
Mario
Key3
00134
00127
00140
00124
00120
00130
Key4
9
8
5
7
6
6
1
2
3
4
5
6
10
ALGORITMI DI ORDINAMENTO
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) + 2) +3)+…+ 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
11
ALGORITMI DI ORDINAMENTO
Iterazione e ricorsione (2)
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.
Esempio: somma i primi n iteri
Sn= n + Sn-1 = n + somma dei primi (n-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).
12
ALGORITMI DI ORDINAMENTO
Esempio di funzione ricorsiva:
Sn= n + Sn-1
somma dei primi n iteri
n + soluzione del problema della somma dei primi (n-1) iteri
“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
Sn= n+(n-1)+Sn-2
Procedendo in queste scomposizioni si giunge fino all’istanza banale del
problema S1= 1
Sn= n+(n-1)+(n-2)+(n-3)+…+1
Osserviamo che nella ricorsione, a differenza dell’iterazione, non si dispone
di un risultato parziale finché non si è giunti fino all’istanza elementare
13
ALGORITMI DI ORDINAMENTO
Selection-sort (ordinamento per 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 ordinata | parte da ordinare
•cerchiamo l’elemento minimo nella parte non ordinata e lo scambiamo
con il primo della parte non ordinata
14
ALGORITMI DI ORDINAMENTO
Selection-sort
Parte iniziale ordinata | parte da ordinare
I iterazione:
A[1..n] non ordinato, cerca minimo di
A[1..n] e scambialo con A[1]. Quindi: A[1] | A[2..n]
II 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 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]
Per 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 A ORDINATO!
15
ALGORITMI DI ORDINAMENTO
Esempio selection-sort:
Sia A un array di 6 elementi da ordinare in modo crescente
j=2
11
11
1
5
11
1
7
j=3 j=4
j=3
j=4 j=5
15 15
11
11
7 19
min=1
min=2
min=2min=3
min=3
min=4 min=5
La parte sinistra del
vettore è già ordinata
1
5
15
11
7
temp
j=6
j=6
i=4
i=2
i=5
i=1
i=3
SelectionSort(A, min,
temp)
for i=1 to n-1 do
min
:=
min
:=
iii i i i
min
min
min
min
:=
:=
:=
:=
for j=i+1 to n do
for
for
for
j=i+1
j=i+1
j=i+1
j=i+1
to
to
ton
to
nndo
do
ndodo
forfor
j=i+1
to
n
do
If A(min)>A(j)
If
A(min)>A(j)
IfA(min)>A(j)
A(min)>A(j)
IfIfIfA(min)>A(j)
A(min)>A(j)
then
then
then
thenthen
then
min
min
min
min
:=
:=
:=
jj:=
jj j := j
min
min
:=
endif
endif
endif
endif
endif
endif
endfor
temp
==A[min]
temp
temp
temp
==A[min]
A[min]
A[min]
A[min]
= A[i]
A[min]
A[min]
A[min]
===A[i]
A[i]
A[i]
A[i] A[i]
=A[i]
temp
A[i]
===temp
temp
temp
endfor
16
Problema:
ALGORITMI DI ORDINAMENTO
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
porzione
endfor
procedure ord_sel_max(in:n;
inout:a)
var n,indice_max:integer
var a:array(1..n)of character
begin
for i=n,2 step=-1 do
indice_max := 1
for k=2,i do
if a(indice_max)<a(k)then
indice_max := k
endif
endfor
scambiare_c(a(i),a(indice_max))
endfor
end
17
ALGORITMI DI ORDINAMENTO
Analisi del selection-sort (1)
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.
….
18
ALGORITMI DI ORDINAMENTO
Analisi del selection-sort (2)
Durante la n-1 iterazione bisogna effettuare 1 confronti per determinare il
minimo tra 2 elementi.
 n-i = (n-1)+(n-2)+…+2+1 = n(n-1)/2
n-1
Quindi il numero di confronti è :
i=1
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)
19
ALGORITMI DI ORDINAMENTO
Insertion-sort (ordinamento per 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
20
ALGORITMI DI ORDINAMENTO
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
21
ALGORITMI DI ORDINAMENTO
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
j=0
j=0 j=1
j=1 j=2
j=2 j=3
j=3 j=4
A
j=5
InsertionSort(A,n, temp)
for i=2 to n do
temp
:=:=a(i)
11
5 11
1
11 11
5
1 11
11
7
15 15
7 19
i=2
i=3
i=4
i=5
i=6
temp
temp
temp
:=
:=
a(i)
a(i)
a(i)
j :=
j j:=
ji-1
:=
:=
i-1
i-1
i-1
while j>=1 and temp<a(j)
i=2
i=3 i=4
i=5 i=6
a(j+1)
:=
a(j)
La
Lacondizione
condizione
condizione
a(j+1)
a(j+1)
a(j+1)
:=
:=:=
a(j)
a(j)
a(j)
La
La condizione
falsa
falsa
j:=
:=
j-1
èèèfalsa
è falsa
jj:=
j:=
j-1
j-1
j-1
end while
19
7
15
5
1
a(j+1) :=
:= temp
temp
a(j+1)
a(j+1)
:=
temp
temp
endfor
endfor
end
L’insertion-sort è un algoritmo di ordinamento stabile
22
ALGORITMI 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
23
ALGORITMI DI ORDINAMENTO
Algoritmi di ordinamento stabili
Se 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)
Esempio (Alg. Stabile) : ordinare un vettore di voti scolastici
voto Carlo
voto Luca
voto Gina
voto Rita
voto Mario
voto Paolo
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
5
7
5
voto Carlo
8
5
voto Rita
5
6
6
7
voto Mario voto Luca
7
7
voto Paolo
8
voto Gina
Si conserva l’ordinamento sul nome!
24
ALGORITMI DI ORDINAMENTO
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
voto Carlo
voto Luca
5
7
voto Gina
8
voto Rita
voto Mario
5
6
voto Paolo
7
for i=n,2 step=-1 do
determinare l’elemento massimo
della porzione 1..i dell’array
metterlo all’ultimo posto della
porzione
endfor
voto Carlo voto
votoMario
Rita
Luca
a[1]
a[2]
voto
votoGina
Paolo
Rita
voto Rita
voto Mario
voto Paolo
a[3]
a[4]
a[5]
a[6]
Si perde l’ordinamento sul nome: algoritmo non-stabile
5
5
voto Rita
75
6
5
8
7
5
6
5
7
voto Carlo voto Mario voto Paolo
6
7
voto Luca
7
8
i=5i=4
i=6 i=3
i=2
voto Gina
25
ALGORITMI DI ORDINAMENTO
Analisi delle prestazioni dell’insertion-sort (1)
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.
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.
26
ALGORITMI DI ORDINAMENTO
Analisi delle prestazioni dell’insertion-sort(2)
Analizziamo il caso peggiore considerando l’ordinamento delle carte da
gioco:
 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
Quindi il numero di confronti totali su di un array di dimensione n è:
n-1
 i = 1 + 2 + 3 + ... + n-1 = n(n-1)/2
i=1
27
ALGORITMI DI ORDINAMENTO
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.
28
ALGORITMI DI ORDINAMENTO
Bubble-sort (ordinamento a bolle)
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).
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)
29
ALGORITMI DI ORDINAMENTO
Esempio: Sia A il vettore da ordinare
BubbleSort(A,n,scambio,temp)
i:=1
repeat
La condizione
è falsa
j=2
A
11
5
1
j=3
j=4
j=4 j=5
11
11 11
1
5
1 11
11
7
15
7 15
7 19
15
Scambio=0
j-1=1
j-1=1j-1=2j-1=3
j-1=3
j-1=4
Vettore Ordinato!
5
1
7
7
temp
Scambio=0
Scambio=1
scambio:=
scambio:=00
for j=i+1 to n do
if (A[j] < A[j-1]) then
temp:=A[j]
temp:=A[j]
A[j]:=A[j-1]
A[j-1]:=temp
A[j-1]:=temp
scambio:=1
scambio:=1
endif
endfor
until scambio=0
end
Il bubble-sort è un algoritmo stabile come l’insertion-sort
30
ALGORITMI DI ORDINAMENTO
Analisi delle prestazioni del bubble-sort(1)
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.
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.
31
ALGORITMI DI ORDINAMENTO
Analisi delle prestazioni del bubble-sort(1)
Nel caso peggiore il bubble sort effettua i seguenti confronti:
 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
Quindi nel caso peggiore il numero di confronti e scambi su di un array di
dimensione n è:
 (n-i) = n  1 -  i = n(n-1)-n(n-1)/2 = n(n-1)/2
n=1
n=1
n=1
i=1
i=1
i=1
32
ALGORITMI DI ORDINAMENTO
Algoritmi di ordinamento ricorsivi
“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.
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
33
ALGORITMI DI ORDINAMENTO
Selection-Sort ricorsivo
Gli algoritmi di ordinamento visti finora possono essere realizzati anche con
metodi ricorsivi. La ricorsione è un metodo molto più elegante
dell’iterazione
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 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]
34
ALGORITMI DI ORDINAMENTO
Algoritmo ricorsivo del Selection-Sort
SelectRic(int A[], int inizio)
Metodo ricorsivo Selection-Sort:
Metto il minimo in prima posizione, poi
ordino quello che resta del vettore.
{
int i, minpos; minpos=inizio;
Cerco il minimo fra A[inizio],
A[inizio+1], ... , A[A.length-1]
for(i=inizio; i<A.length; i++)
{
if(A[i]<A[minpos])
Lo metto in A[inizio] (faccio lo
scambio)
Faccio la chiamata
passando inizio+1
minpos=i;
int temp=A[inizio];
ricorsiva
A[inizio]=A[minpos];
A[minpos]=temp;
}
Manca ancora
ricorsione!
il
caso
base
della
SelectRic(A, inizio+1);
}
35
ALGORITMI DI ORDINAMENTO
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.
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];
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!)
A[inizio]=A[minpos];
A[minpos]=temp;
SelectRic(A, inizio+1);
}
36
ALGORITMI DI ORDINAMENTO
Bubble-Sort ricorsivo
Nell’ordinamento a bolle dobbiamo far risalire gli
elementi più leggeri (più piccoli) fino alla cima
del vettore.
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.
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);
}
Manca il caso base!
37
ALGORITMI DI ORDINAMENTO
Bubble-Sort: caso base
BubbleRic(A[], fine) {
int i, temp;
La parte di vettore da ordinare diventa
sempre più piccola a ogni invocazione
ricorsiva.
if(fine==0) return;
// CASO BASE
for(i=0; i<=fine-1; i++)
if(A[i]>A[i+1]) {
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!)
temp=A[i];
A[i]=A[i+1];
A[i+1]=temp;
}
BubbleRic(A, fine-1);
}
38
ALGORITMI DI ORDINAMENTO
Insertion-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
39
ALGORITMI DI ORDINAMENTO
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
}
}
40
ALGORITMI DI ORDINAMENTO
Prestazioni degli algoritmi di ordinamento
(risultati sperimentali)
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.
41
ALGORITMI 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.
42
ALGORITMI DI ORDINAMENTO
Implementazione degli algoritmi di sorting
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
43
ALGORITMI DI ORDINAMENTO
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-D
ALGORITMI DI ORDINAMENTO
Riferimenti
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