 Ciò motiva lo studio degli algoritmi di Ciò motiva lo studio degli algoritmi di ordinamento.

Sez. 2: Ordinamento

 La consultazione di banche dati è sempre più cruciale in tutte le applicazioni dell’Informatica.

 Se vogliamo consultare spesso un vettore t =

<t ₁ , .., t _n > di dati è conveniente tenere t ordinato.

 Ciò motiva lo studio degli algoritmi di Ciò motiva lo studio degli algoritmi di ordinamento.

ordinamento.

Tempi di accesso ai dati a confronto (casi medi)

Lunghezza vettore V

10 100 1,000 1,000,000 n Tempo

(V disordinato)

10 100 1,000 1,000,000 n Tempo

(V ordinato)

3 6 9 19 log ₂ n

Il vantaggio nell’avere un vettore ordinato é tanto più

marcato quanto più grande é la banca dati (ed oggi le

banche dati tendono ad essere enormi).

Tempi di accesso ai dati a confronto (cenni di spiegazione)

 Sia t non ordinato. Per trovare un dato x in t dobbiamo passare gli elementi di t ad uno ad uno.

 Questo richiede in media n/2 passi se x è in t, ed n passi se x non è in t (dobbiamo esaminare tutto t prima di essere sicuri che x non c’è).

 Sia t ordinato. Possiamo cercare x nel punto medio t m di t. Se x = t m , siamo a posto; se x < t m , dobbiamo continuare la ricerca in <t 1 , .., t m-1 >; altrimenti, in <t m-1 , .., t n >. Ripetendo questo procedimento, ad ogni passo la lunghezza del vettore in cui cercare si dimezza.

 Nel caso peggiore occorrono log 2 (n) passi (occorrono log 2 (n)

dimezzamenti per far scendere n ad 1).

Ordinamento: terminologia.

 Chiave = la parte del dato d che serve per confrontare due dati Chiave nell’ordine.

– Se d è la scheda di un’automobile, la chiave di d è la targa dell’auto (e l’ordine è quello ascii).

– Se d è la scheda di una persona, la chiave di d è il nome della persona (e l’ordine è quello alfabetico).

– Se d è la scheda di uno studente, la chiave di d è la matricola dello studente (e l’ordine è quello numerico).

 Studieremo la complessità di in tempo, misurata in base a: il

numero di confronti tra chiavi usato + il numero di spostamenti

eseguiti sui dati.

Ordinamento: conclusioni

 Abbiamo motivato lo studio degli algoritmi di ordinamento con ragioni di complessità.

 Utilizzeremo ora di nuovo la complessità

per confrontare vari algoritmi di

ordinamento tra loro, e sceglierne il

migliore.

Sez. 3: BubbleSort

(ordinamento “a bolla”)

 Il BubbleSort trasporta il massimo dei primi n elementi nella posizione n, poi il massimo tra i primi n-1 nella posizione n-1, e così via, finché il vettore è ordinato.

 Il trasporto del massimo tra i primi i elementi nella posizione i avviene scorrendo il vettore un passo alla volta, e portandoci dietro l’elemento più grande tra quelli incontrati (che quindi risale di un passo alla volta, “come una bolla”, fino a raggiungere la posizione i).

 Ciò si ottiene scambiando il primo elemento col secondo (a

meno che il secondo sia maggiore), poi il secondo con il terzo

(a meno che il terzo sia maggiore), e così via fino all’i-esimo.

Esempio di BubbleSort

(su un vettore con chiavi numeriche, n=4)

Partenza 7 7 7 7  0  45 12

scambio

(tra 77 e 0) 0 7 7 7 7  45  12

scambio

(tra 77 e 45) 0 45 7 7 7 7  12 

scambio

(tra 77 e 12) 0 0   45 12 7 7 7 7 s s t t op o p Con 3 confronti abbiamo trasportato il massimo tra i primi quattro elementi in quarta posizione.

Ora trasporteremo il massimo tra i primi tre elementi

in terza posizione.

Esempio di BubbleSort

(continua)

scambio

(tra 77 e 12) 0 0   45 12 7 7 7 7 s s t t o o p p no scambio

(0 < 45) 0 4 4 5 5  12  77

scambio

(tra 45 e 12) 0 0   12 4 4 5 5 s s t t o o p p 77

no scambio

(0 < 12) 0 1 1 2 2 st s t op o p 45 77

Con due confronti abbiamo trasportato il massimo tra i primi tre elementi in terza posizione; strada facendo, abbiamo abbandonato lo 0 e lo abbiamo sostituito con il 45.

Lo stesso per il massimo tra i primi due elementi.

Complessità del BubbleSort (in tempo)

 Trasportare il massimo dei primi i elementi in posizione i richiede i-1 confronti (uno tra il primo ed il secondo, uno tra il secondo e il terzo, ... uno tra gli elementi i-1 ed i).

 Il numero totale di confronti è (n-1) + (n-2) + ... = n(n-1)/2.

 Ogni confronto può richiede o no uno scambio.

 Il numero minimo, medio, massimo di scambi è quindi:

– 0, n(n-1)/4, n(n-1)/2.

 Confronti e scambi crescono rapidamente con n. Per n=mille

occorrono 500 mila confronti e 250 mila scambi; per n=un

milione occorrono 500 miliardi di confronti e 250 miliardi di

scambi.

BubbleSort: conclusioni

 L’analisi della complessità mostra che il BubbleSort non è adatto per banche dati molto grandi (n=un milione o più) oppure usate di continuo.

 Tuttavia, il BubbleSort ha il vantaggio di essere molto semplice da realizzare.

 Il BubbleSort si può quindi usare su

piccole banche dati a cui accedo

frequentemente, e che non modifico spesso.

Sez. 4: InsertSort

(ordinamento “per inserzione”)

 L’InsertSort comincia ordinando i primi due elementi.

 Quindi inserisce il terzo elemento tra i primi due (ora ordinati) in modo da rispettare l’ordine.

 Quindi inserisce il quarto tra i primi tre (ora ordinati) in modo da rispettare l’ordine.

 E così via, fino ad inserire l’n-esimo elemento

tra i primi n-1.

Esempio di InsertSort

(su un vettore con chiavi numeriche, n=4)

Partenza 77 0 45 12

ordinamento

(primi due el.) 0 qui 77 45 12

inserimento

(del terzo el.) 0 77 45 12

0 45 ^qui 77 12

Per inserire lo 0 abbiamo dovuto trasportare il 77

avanti di un passo. Per inserire il 45 abbiamo dovuto

Esempio di InsertSort

(continua)

inserimento

(quarto el.) 0 0 45 77  1 1 2 2

0 1 1 2 2 q q u u i i 45 77

Per inserire il 12 abbiamo dovuto spostare gli elementi >

12 avanti di un passo.

Complessità dell’InsertSort (in tempo)

 Inserire un elemento x in una lista di i elementi già ordinati richiede di scorrere tali i elementi dal fondo verso l’inizio, fino a trovare l’elemento  x piú a destra. Questo richiede:

– Confronti = 1, Spostamenti = 0 nel caso migliore (inserimento al fondo; es.: vettore già ordinato);

– Confronti = i/2, Spostamenti = i/2 nel caso medio (inserimento a metà);

– Confronti = i, Spostamenti = i nel caso pessimo (inserimento all’inizio; es.: vettore in ordine decresc.).

 Totale InsertSort (somma dei precedenti per 1  i  n-1):

– Confr. = n-1 (min), n(n-1)/4 (medio), n(n-1)/2 (max)

– Spost. = 0 (min), n(n-1)/4 (medio), n(n-1)/2 (max)

InsertSort: conclusioni

 L’InsertSort si rivela nettamente migliore del BubbleSort.

 Infatti, in base allo studio di complessità, per ogni scambio richiesto dal BubbleSort, l’InsertSort richiede uno spostamento. Uno spostamento è 3 volte più veloce di uno scambio.

 Tuttavia, anche per l’InsertSort, il tempo utilizzato cresce con il quadrato della dimensione del vettore da ordinare. Per n = 1,000,000 occorrono 250 miliardi di spostamenti.

 Dunque anche l’InsertSort, benche sia da due a tre volte più

veloce del BubbleSort, non è adatto per banche dati molto

grandi oppure usate di continuo.