si considera una sequenza di N dati d 0 d 1 d 2 ... d N−1

(1)

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 0 d 1 d 2 ... 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

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

(2)

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

Ordinamento

data una sequenza di dati

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

generare un altra sequenza

d k

0

d k

1

d k

2

· · · d N−2 d k

N −1

tale per cui

K(d k

0

) ≤ K(d k

1

) ≤ K(d k

2

) ≤ · · · ≤ K(d k

_{N −2}

) ≤ k(d k

_{N −1}

)

Ordinamento per selezione

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

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;

} }

(3)

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

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

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)

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

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

(4)

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

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

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

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

si considera una sequenza di N dati d 0 d 1 d 2 ... d N−1

Ricerca e ordinamento

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

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 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 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 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);

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

operatori di relazione ed uguaglianza

operatori di uguaglianza

uguaglianza tra istanze

relazione d’ordine

si confronta un dato alla volta in maniera

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

si confronta l’elemento di mezzo con il dato cercato

se non è tale dato

si termina quando si trova l’elemento oppure si ha un sotto-array vuoto

effettuare un confronto con l’elemento centrale

effettuare una ricerca in un array di dimensione n/2 per cui

dati N elementi

per ordinare i rimanenti N-1 dati ((N-1)+3)

e via fino a N=2

= ¹ ₂ N ² + ⁹ ₂ N − 4

complessità O(n ² )