Ricerca e ordinamento
Paolo Bison
Fondamenti di Informatica Ingegneria Meccanica
Università di Padova A.A. 2008/09
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.1
Struttura dei dati
si considera una sequenza di N dati d 0 d 1 d 2 ... d N−1 memorizzati in un array
si deve avere una relazione d’uguaglianza = ed una d’ordine ⊑ applicabile
ai singoli dati (d i = d j d i ⊑ d j )
ad elementi k i ( k i = k j k i ⊑ k j ) calcolato ciascuno dal corrispondente dato d i
k i = K( d i ) con 0 ≤ i < N
• key (chiave)
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.2
Rappresentazione dei dati
user-defined type (struttura) type,public :: datum
integer :: key
character(len=256) :: info ! payload end type
chiave codificata in maniera esplicita
modulo dbarray.f90
Ricerca
trovare in una sequenza di dati
d 0 d 1 d 2 ... d N−1
un particolare elemento ¯d, se esiste, tale per cui si abbia
¯d=d i con 0 ≤ i < N
ricerca per chiave
data un chiave ¯k trovare il dato ¯d tale per cui
Ricerca lineare
cercare il valore 12 nel seguente array
18 0 17 12 8 20
18 0 17 12 8 20
18 0 17 12 8 20
18 0 17 12 8 20
18 0 17 12 8 20
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.5
Ricerca lineare
algoritmo
si confronta un dato alla volta in maniera sequenziale finché non si trova l’elemento cercato o termina la sequenza
codice Fortran
function ricerca(a,key,ris) result(trovato) type(datum),dimension(:),intent(in) :: a integer,intent(in) :: key
type(datum),intent(out) :: ris logical :: trovato
integer :: i,n n=ubound(a,1) do i=1,n
if (a(i)%key==key) then; exit; end if end do
trovato=i<=n
if (trovato) then; ris=a(i); end if end function ricerca
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.6
Ricerca lineare: prestazioni
valutazione numero di accessi all’array
se il dato cercato non è presente, sono necessari n accessi
se il dato è presente, il numero di accessi dipende dalla posizione del dato nell’array
• in media n/2
complessità
O(n)
Ricerca binaria
cercare il valore 12 nel seguente array ordinato
5 9 11 12 17 21
5 9 11 12 17 21
5 9 11 | 12 17 21
5 9 11 | 12 17 21
5 9 11 | 12 | 17 21
5 9 11 | 12 | 17 21
Ricerca binaria
algoritmo
si confronta l’elemento di mezzo con il dato cercato
se non è tale dato
• se è maggiore si cerca in modo binario nel sotto-array a sx
• altrimenti nel sotto-array di dx
si termina quando si trova l’elemento oppure si ha un sotto-array vuoto
dicotomica o per bisezione
applicabile solo se i dati sono ordinati
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.9
Ricerca binaria: codice Fortran
function ricerca(a,key,ris) result(trovato) type(datum),dimension(:),intent(in) :: a integer,intent(in) :: key
type(datum),intent(out) :: ris logical :: trovato
integer :: i,j,k,n n=ubound(a,1); i=1; j=n do
k = (i+j)/2
if ((a(k)%key==key).or. (i>j)) then exit
end if
if (a(k)%key>key) then j=k-1
else i=k+1 end if end do trovato=i<=j
if (trovato) then; ris=a(k); end if end function ricerca
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.10
Ricerca binaria: prestazioni
numero di confronti necessari per trovare un dato
dato un array di dimensione n si deve
effettuare un confronto con l’elemento centrale
effettuare una ricerca in un array di dimensione n/2 per cui
T (n) = T (n/2) + 1 la cui soluzione è
T (n) = 1 + log 2 n
complessità
O(log n)
lineare vs. binaria
tempi di esecuzione in sec key lineare binaria
1 0.43 0.48
10000000 0.74 0.47 20000000 1.06 0.51
0 1.07 0.52
Ordinamento
data una sequenza di dati
d 0 d 1 d 2 · · · d N−2 d N−1 generare un altra sequenza
d k
0d k
1d k
2· · · d N −2 d kN−1
tale per cui
K ( d k0) ≤ K( d k1) ≤ K( d k2) ≤ · · · ≤ K( d kN−2) ≤ k( d kN−1)
) ≤ K( d k2) ≤ · · · ≤ K( d kN−2) ≤ k( d kN−1)
) ≤ k( d kN−1)
ordinamento in loco
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.13
Ordinamento per selezione
3 -7 5 7 -1
3 -7 5 7 -1
-7
|3 5 7 -1
-7
|3 5 7 -1
-7 -1
|5 7 3
-7 -1
|5 7 3
-7 -1 3
|7 5
-7 -1 3
|7 5
-7 -1 3 5
|7
-7 -1 3 5
|7
-7 -1 3 5 7
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.14
Ordinamento per selezione: algoritmo
dato un array di N elementi si cerca il dato più piccolo
si scambia questo elemento con il primo
si considera il sotto-array di dimensione N − 1 composto da tutti i dati eccetto il primo
si riapplica il medesimo algoritmo
Ordinamento per selezione: codice Fortran
subroutine sort(a)
type(datum),dimension(:),intent(inout) :: a integer :: i,j,k
integer :: n type(datum) :: x n=ubound(a,1) do i=1,n-1
k = i; x = a(i) do j=i+1,n
if (a(j)%key<x%key) then k = j; x = a(j) end if
end do
a(k) = a(i); a(i) = x end do
end subroutine sort
Ordinamento per selezione: prestazioni
calcolo del numero di accessi
dati N elementi
• N accessi per trovare il minimo
• 3 accessi per lo scambio in totale, ( N +3)
per ordinare i rimanenti N -1 dati (( N -1)+3)
e via fino a N =2
totale accessi
( N +3)+(( N -1)+3))+ · · · +(3+3)+(2+3)
= 1 2 N 2 + 9 2 N − 4
complessità O(n 2 )
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.17
Ordinamento per inserimento
3 -7 5 7 -1
3
|-7 5 7 -1
3
|-7 5 7 -1
-7 3
|5 7 -1
-7 3
|5 7 -1
-7 3 5
|7 -1
-7 3 5
|7 -1
-7 3 5 7
|-1
-7 3 5 7
|-1
-7 3 5 -1 7
|-7 3 -1 5 7
|-7 -1 3 5 7
| Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.18Ordinamento per inserimento: algoritmo
si eseguono N − 1 passi
ad ogni passo si considera i dati divisi in due parti
una ordinata 0 ≤ k < i
una non ordinata i ≤ m ≤ N − 1
si prende il primo dato presente nella parte non ordinata e lo si inserisce in quella ordinata
per inserirlo si sposta a dx dati che siano maggiori di quello da inserire
ad ogni passo la parte ordinata aumenta di una unità mentre quella non ordinata diminuisce di 1
Ordinamento per inserimento: codice
subroutine sort(a)
type(datum),dimension(:),intent(inout) :: a integer :: i,j
integer :: n type(datum) :: x n=ubound(a,1) do i=2,n
x = a(i); j=i-1 do
if (j==0) then; exit; end if if (a(j)%key<=x%key) then
exit end if a(j+1)=a(j) j=j-1 end do a(j+1) = x
Ordinamento per inserimento: prestazioni - I
caso migliore
dati già ordinati
nessuna iterazione del ciclo interno, solo un accesso per il confronto
il ciclo esterno viene eseguito N − 1 volte
totale accessi: 3(N − 1)
complessità O(n)
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.21
Ordinamento per inserimento: prestazioni - II
caso peggiore
dati ordinati a rovescio
il ciclo interno deve spostare tutti i dati già ordinati
totale accessi: 2(N − 1) + 3N(N−1) 2
complessità O(n 2 )
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.22
Ordinamento per inserimento: prestazioni - III
caso medio
dati in ordine casuale
il ciclo interno deve spostare in media metà dei dati già ordinati
totale accessi: 2(N − 1) + 3N(N−1) 4
complessità O(n 2 )
Bubble sort
3
-7
5
7
-1 3
←
-75
7
-1 3
←
-75
7
-1 3
←
-75
-1
7 3
←
-75
-1
7 3
←
-7-1
5
7 3
←
-7-1
5
7 3
←
-7-1
5
7 -7
3
←
-15
7 -7
3
←
-15
7 -7
3
←
-15
7 -7
3
←
-15
7 -7
-1
3
←
57 -7
-1
3
←
57 -7
-1
3
5
←
7-7
-1
3
5
←
7-7
-1
3
5
7
Bubble sort: algoritmo
a turno si compara coppie adiacenti di dati scambiandoli se necessario
si ripete questo passo per tutti i possibili confronti oppure finché non è avvenuto nessun scambio
dati più piccoli risalgono verso l’inizio della sequenza
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.25
Bubble sort: codice
subroutine sort(a)
type(datum),dimension(:),intent(inout) :: a integer :: i,j
integer :: n type(datum) :: x n=ubound(a,1) do i=2,n
do j=n,i,-1
if (a(j-1)%key>a(j)%key) then x=a(j)
a(j)=a(j-1) a(j-1)=x end if end do end do
end subroutine sort
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.26Bubble sort: prestazioni
il ciclo esterno viene eseguito N − 1 volte
il numero di iterazioni del ciclo interno diminuisce di uno ad ogni iterazione di quello esterno
totale accessi (caso migliore):
2 (N−2)(N−3) 2
complessità O(n 2 )
Merge sort
3 -7 5 7 -1
3 -7 | 5 7 -1
3 -7 | 5 | 7 -1
| X 7 -1 X
| X 5 -1 X X 7 -7 X X 3 -1 X X 5 X 7
-7 -1 3 5 7
-7 -1 3 5 7
Merge sort: algoritmo
se la sequenza è formata da un solo dato è ordinata
altrimenti
si divide la sequenza in due sotto-sequenze (circa) uguali
si ordina la prima sotto-sequenza con il merge sort
si ordina la seconda sotto-sequenza con il merge sort
si fondono (merge) le due sequenze ordinate costruendo una nuova sequenza ordinata
• prendendo un dato alla volta dalla sotto-sequenza il cui primo dato è il minore
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.29
Merge sort: codice - I
subroutine sort(a)
type(datum),dimension(:),intent(inout) :: a call mergeSort(a,size(a,1))
end subroutine sort
recursive subroutine mergeSort(a,N)
type(datum),dimension(:),intent(inout) :: a integer,intent(in) :: N
integer :: mid
type(datum),dimension(N/2) :: left type(datum),dimension(N-N/2) :: right if (N>1) then
mid=N/2 left=a(1:mid) right=a(mid+1:N)
call mergeSort(left,size(left,1)) call mergeSort(right,size(right,1)) call mergeOrder(a,left,right) end if
end subroutine mergeSort
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.30
Merge sort: codice - II
subroutine mergeOrder(a,b,c) ! combina b e c in a in maniera ordinata type(datum),dimension(:),intent(out) :: a
type(datum),dimension(:),intent(in) :: b,c; integer :: ia,ib,ic,l ia=1; ib=1; ic=1;
do
if (ib>size(b,1) .or. ic>size(c,1)) then exit
end if
if (b(ib)%key<c(ic)%key) then a(ia)=b(ib); ib=ib+1;
else
a(ia)=c(ic); ic=ic+1;
end if ia=ia+1 end do
do l=ib,size(b,1) ! eseguito se size(b) >size(c) a(ia)=b(ib); ib=ib+1;ia=ia+1
end do
do l=ic,size(c,1)! eseguito se size(c) >size(b) a(ia)=c(ic); ic=ic+1;ia=ia+1
Merge sort: prestazioni
numero di accessi
le copie di array richiedono 2N accessi
ogni invocazione ricorsiva richiede T (N/2) accessi
fusione necessita di 3N accessi ( N per leggere e 2N per scrivere)
totale accessi :
T (N) = T (N/2) + 5N T (N) = N + 5N log 2 (N)
complessità O(n log(n))
Confronto tra ordinamenti
migliore medio peggiore
selection n 2 n 2 n 2
insertion n n 2 n 2
bubble n 2 n 2 n 2
merge n log n n log n n log n
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.33
Prestazioni
tempi di esecuzione in sec per ordinare un array di 10000 elementi:
-1 2 -3 4 -5 ... -9995 9996 -9997 9998 -9999 10000
lineare inserimento bubble merge
9.92 17.31 25.70 0.10
Ricerca e ordinamento, Paolo Bison, FI08, 2008-09-29 – p.34
