Struttura dei dati

Ricerca e ordinamento

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05

Universit`a di Padova

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.1/33

Struttura dei dati

 si considera una sequenza di N dati d ₀ d ₁ d ₂ ... d N −1

memorizzati in un array

 si deve avere una relazione d’uguaglianza = ed una d’ordine v applicabile

 ai singoli dati (d i =d j d i vd j )

 ad elementi k i (k i = k j k i v k j ) calcolato ciascuno dal corrispondente dato d i

k i = K(d i ) con 0 ≤ i < N

• key (chiave)

Confronto tra dati in Java

 tipi base

 operatori di relazione ed uguaglianza

 oggetti

 operatori di uguaglianza

verifica se è la medesima istanza

 uguaglianza tra istanze

metodo boolean equals(Object)

• il metodo definito nella classe Object equivale a ==

 relazione d’ordine

metodo int compareTo(Object) dell’interfaccia Comparable

• non è definito nella classe Object

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.3/33

Rappresentazione dei dati

 interfaccia KeyComparable

public interface KeyComparable { Comparable key(); }

 classe Datum class Datum

implements KeyComparable{

int num; String info;

public Datum(int i,String st) { num = i; info = st; }

public Comparable key()

{ return new Integer(num);}

}

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 K( ¯ d) = ¯k

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.5/33

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 lineare

 algoritmo

 si confronta un dato alla volta in maniera

sequenziale finché non si trova l’elemento cercato o termina la sequenza

 codice Java

Object linearSearch(

KeyComparable[] data, Comparable key){

int i;

for(i=0;i<data.length;i++)

if (data[i].key().equals(key)) return data[i];

return null;

}

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.7/33

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 e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.9/33

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 binaria: codice Java

Object binarySearch(KeyComparable[] data,Comparable key) { return binsearch(data,key,0,data.length-1); }

Object binsearch(KeyComparable[] data,Comparable key, int min,int max) {

int mid;

if (min>max) return null;

mid =(min+max)/2;

if (data[mid].key().equals(key)) return data[mid];

if (data[mid].key().compareTo(key)>0) return binsearch(data,key,min,mid-1);

else

return binsearch(data,key,mid+1,max);

}

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.11/33

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 ₂ n

 complessità

O(log n)

Ordinamento

 data una sequenza di dati

d 0 d 1 d 2 · · · d N −2 d N −1

generare un altra sequenza

d k

d k

d k

· · · d N −2 d k

tale per cui

K(d k

) ≤ K(d k

) ≤ K(d k

) ≤ · · · ≤ K(d k

) ≤ k(d k

)

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.13/33

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

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

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.15/33

Ordinamento per selezione: codice

void selectionSort(KeyComparable[] data){

int i,j,k; KeyComparable min,t;

for (i=0;i<data.length-1;i++){

// ricerca del minimo k = i; min=data[k];

for (j=i+1;j<data.length;j++){

t=data[j];

if (t.key().compareTo(min.key())<0) { k = j; min = t;

} }

// scambio

data[k]=data[i]; data[i]=min;

}

}

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)

= ¹ ₂ N ² + ⁹ ₂ N − 4

 complessità O(n ² )

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.17/33

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

-7 -1 3 5 7

Ordinamento 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

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.19/33

Ordinamento per inserimento: codice

void insertionSort(KeyComparable[] data){

int i,j; KeyComparable x;

for (i=1;i<data.length;i++){

x=data[i]; j=i-1;

// spostamento di elementi minori di x while(j>=0 &&

data[j].key().compareTo(x.key())>0){

data[j+1]=data[j]; j=j-1;

}

// inserimento dato data[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, A.A. 2004-05, 2004-11-27 – p.21/33

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)} ₂

 complessità O(n ² )

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)} ₄

 complessità O(n ² )

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.23/33

Bubble sort

3

-7

5

7

-1 3

← -7

5

7

-1 3

← -7

5

7

-1 3

← -7

5

-1

7 3

← -7

5

-1

7 3

← -7

-1

5

7 3

← -7

-1

5

7 3

← -7

-1

5

7 -7

3

← -1

5

7 -7

3

← -1

5

7 -7

3

← -1

5

7 -7

3

← -1

5

7 -7

-1

3

← 5

7 -7

-1

3

← 5

7 -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, A.A. 2004-05, 2004-11-27 – p.25/33

Bubble sort: codice

void bubbleSort(KeyComparable[] data){

int i,j; KeyComparable x;

for (i=1;i<data.length;i++)

for (j=data.length-1;j>=i;j--)

if (data[j-1].key().compareTo(data[j].key())>0) { // scambio

x=data[j];data[j]=data[j-1];data[j-1]=x;

}

}

Bubble 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 ² )

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.27/33

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, A.A. 2004-05, 2004-11-27 – p.29/33

Merge sort: codice - I

void mergeSort(KeyComparable[] data){

int mid; KeyComparable left[],right[];

if (data.length>1){

mid = data.length / 2;

left = new KeyComparable[mid];

right = new KeyComparable[data.length-mid];

System.arraycopy(data,0,left,0,mid);

System.arraycopy(data,mid,right,0,data.length-mid);

mergeSort(left);

mergeSort(right);

merge(data,left,right);

}

}

Merge sort: codice - II

void merge(KeyComparable[] a, KeyComparable[] b, KeyComparable[] c){

int ia=0,ib=0,ic=0;

while (ib<b.length && ic<c.length)

if (b[ib].key().compareTo(c[ic].key())<0) a[ia++]=b[ib++];

else

a[ia++]=c[ic++];

while (ib<b.length ) a[ia++]=b[ib++];

while (ic<c.length) a[ia++]=c[ic++];

}

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.31/33

Merge sort: prestazioni

 numero di accessi

 arraycopy 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 ₂ (N )

 complessità O(n log(n))

Confronto tra ordinamenti

migliore medio peggiore selection n ² n ² n ²

insertion n n ² n ²

bubble n ² n ² n ²

merge n log n n log n n log n

Ricerca e ordinamento, Paolo Bison, A.A. 2004-05, 2004-11-27 – p.33/33