Silvia Rossi

(1)

Lezione n.

Parole chiave:

Corso di Laurea:

Insegnamento:

Email Docente:

A.A. 2009-2010

Silvia Rossi

Algoritmi di Ordinamento

20 Informatica

Programmazione I

srossi@na.infn.it

Bubble Sort

Selection Sort

(2)

Ordinamento di Array

Supponiamo che Vet sia una variabile dichiarata come int Vet[10];

essa ha un indice compreso tra 0 e 9.

Un array monodimensionale di interi è ordinato in ordine crescente se all’aumentare dell’indice aumenta anche il valore

dell’elemento; è ordinato in ordine decrescente se

all’aumentare dell’indice il valore dell’elemento diminuisce; per esempio dei tre vettori

A=[2, 4, 5, 7, 7, 9, 12, 15] B=[2, 5, 8, 3, 7, 11]

C=[15, 9, 8, 6, 5, 5, 3, 1]

A è ordinato in ordine crescente, C lo è in ordine decrescente,

B non è ordinato.

(3)

Ordinamento di Array

Tenendo presente che un vettore di dimensione 1 è sempre

ordinato, per un vettore di dimensione N>1 possiamo dare le seguenti definizioni:

Gli elementi di un vettore sono ordinati in ordine crescente se e solo se per ogni indice i compreso tra 0 e N -2 si ha

A[ i ]<=A[i+1].

Gli elementi del vettore sono ordinati in ordine decrescente se e solo se per ogni indice i compreso tra 0 e N -2 si ha

A[ i ]>=A [i+1].

Le stesse definizioni possono valere sia per i numeri reali (float o

double) che per le stringhe.

(4)

Ordinamento di Stringhe

L’ordinamento per le stringhe è, di solito, quello lessicografico (l’ordine alfabetico) che rispecchia l’ordine ASCII;

• tutte le lettere maiuscole precedono tutte quelle minuscole

Esempio: andare precede andate andare precede correre andare segue Correre

porta precede portamento

Per questo motivo prima di ordinare lessicograficamente un

insieme di parole che possono iniziare anche con una lettera maiuscola occorre convertire tale carattere iniziale in minuscolo prima di eseguire il confronto.

a n d a r e

0 1 2 3 4 5

a n d a t e

(5)

Ordinamento

10 19 9 30 29 12 18

0 1 2 3 4 5 6

19 30 10

29 12 9

18

(6)

Supponiamo di voler ordinare in modo crescente gli elementi dell’array vet; a questo scopo definiamo la seguente procedura:

void Ordina (int[] vet, int N) {

IN : Vettore di interi di dimensione N non ordinato OUT : Vettore di interi ordinato in modo crescente }

Un possibile modo di risolvere il problema dell’ordinamento è pensare di dover iterare la seguente situazione:

• siamo in uno stato in cui nel nostro vettore i primi k elementi si trovano già nel loro posto definitivo, che quindi nel vettore occupano le posizioni da zero a k-1. Operiamo in modo da portare nella posizione k l’elemento giusto

24 36 ……… 87 125 ………. 120 156

0 1 ………… k-1 k ……… N-2 N-1

Tutti ordinati Tutti di valore maggiore agli ordinati

Ordinamento

(7)

Gli elementi compresi tra 0 e k-1 sono:

• ordinati in ordine crescente

• inseriti nella loro posizione definitiva;

• gli elementi da k in poi (disordinati) sono maggiori di quelli compresi tra 0 e k-1.

Scriviamo il ciclo:

for (k=0; k<N; k++)

porta l’elemento giusto nella posizione k

“Gli elementi minori di k sono ordinati e nella loro posizione definitiva” è l’invariante di ciclo

• k è inizializzato a 0 dunque porta l’elemento giusto nella posizione k è banalmente soddisfatto poiché un solo elemento non può essere disordinato (anche se in generale non sarà l’elemento più piccolo).

• Inoltre esso è ovviamente soddisfatto per definizione in uscita da ogni passo.

• Dopo l’ultimo passo k è diventato N-1 il che significa che l’intero vettore è ordinato allorché si esce dal ciclo.

Ordinamento

24 36 ……… 87 125 ………. 120 156

0 1 ………… k-1 k ……… N-2 N-1

(8)

Per “portare l’elemento giusto nella posizione k”

occorrerà in qualche modo scorrere la seconda parte dell’array, quella ancora disordinanta da k in poi,

dunque occorrerà un altro loop.

Ordinamento

24 36 ……… 87 125 ………. 120 156

0 1 ………… k-1 k ……… N-2 N-1

Tutti ordinati Tutti di valore maggiore agli ordinati

(9)

Bubble Sort

(10)

Tecnica di ordinamento a scambio diretto (a coppie)

– Supponiamo che le prime k carte siano ordinate e nella loro posizione definitiva (totalmente ordinate)

– Scorriamo a ritroso le carte rimanenti non ordinate facendo emergere (come una bolla) la più piccola nella posizione k

• scorrere dalla penultima carta alla carta di posizione k, scambiandola con la successiva se maggiore di questa

– Ora le prime k+1 carte sono ordinate … itera l’algoritmo

k

tot. ordinati

non ordinati 0

Bubble Sort

(11)

k

tot. ordinati

non ordinati 0

Bubble Sort

Tecnica di ordinamento a scambio diretto (a coppie)

– Supponiamo che le prime k carte siano ordinate e nella loro posizione definitiva (totalmente ordinate)

– Scorriamo a ritroso le carte rimanenti non ordinate facendo emergere (come una bolla) la più piccola nella posizione k

– Ora le prime k+1 carte sono ordinate … itera l’algoritmo

(12)

Bubble Sort

Tecnica di ordinamento a scambio diretto (a coppie)

– Supponiamo che le prime k carte siano ordinate e nella loro posizione definitiva (totalmente ordinate)

– Scorriamo a ritroso le carte rimanenti non ordinate facendo emergere (come una bolla) la più piccola nella posizione k

– Ora le prime k+1 carte sono ordinate … itera l’algoritmo

k

tot. ordinati

0 non ordinati

(13)

La tecnica adoperata nel bubble sort per portare in posizione k il più piccolo degli elementi compresi tra gli indici k…N-1, consiste nello scambiare di posto tutte le coppie adiacenti ‘disordinate’ partendo dall’indice N-2 fino ad arrivare all’indice k

for(k=0; k<N; k++)

Ciclo esterno: Incrementa k solo quando tutti gli elementi da 0 a k sono ordinati in via definitiva

for (j=N-2; j>=k; j--)

Ciclo Interno: cerca il più piccolo dei valori di vet[j]

compresi tra N-2 e k

if (vet[j] > vet[j+1]) allora scambia (vet[j],vet[j+1]);

Al termine del ciclo interno sarà verificata la condizione: vet[k] è il più piccolo tra tutti gli elementi compresi tra k ed N-1.

Inoltre altri elementi si saranno avvicinati alla loro posizione definitiva.

Bubble Sort

(14)

10 k=0 19 9 30 29 12 18 10 19 9 30 29 12 18 10 19 9 30 12 29 18

10 19 9 12 30 29 18 10 19 9 12 30 29 18 10 19 9 12 30 29 18

9 10 19 12 30 29 18

9 k=1 10 19 12 30 29 18 9 10 19 12 30 18 29 9 10 19 12 18 30 29

9 10 19 12 18 30 29 9 10 12 19 18 30 29 9 10 12 19 18 30 29

9 10 12 19 18 30 29

9 10 12 19 18 29 30 9

10 12 19 18 29 30

9 10 12 19 18 29 30

9 10 12 18 19 29 30

9 10 12 19 18 29 30

10 9 12 19 18 29 30 9 10 12 19 18 29 30

9 10 12 18 19 29 30

k=2

k=3

j=N-2

Bubble Sort

(15)

9 k=4

10 12 18 19 29 30

9 10 12 18 19 29 30

9 k=5

10 12 18 19 29 30

9 10 12 18 19 29 30

k=6

N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2

Bubble Sort

(16)

L’algoritmo è composto da due cicli nidificati.

Applichiamolo al seguente esempio:

indici 0, 1, 2, 3, 4 vet = [6, 8, 11, 5, 7]

CICLO ESTERNO k=0 CICLO INTERNO

j=3 vet[3] > vet[4] : NO è lascia il vettore invariato

j=2 vet[2] > vet[3] : SI è scambia gli elementi; il vettore diventa: [6, 8, 5,11, 7]

j=1 vet[1] > vet[2] : SI è scambia gli elementi; il vettore diventa: [6, 5 ,8, 11, 7]

j=0 vet[0] > vet[1] : SI è scambia gli elementi; il vettore diventa: [5, 6 ,8, 11, 7]

CICLO ESTERNO k=1 CICLO INTERNO

j=3 vet[3] > vet[4] : SI è scambia gli elementi; il vettore diventa: [5, 6 ,8, 7, 11 ] j=2 vet[2] > vet[3] : SI è scambia gli elementi; il vettore diventa [5, 6, 7, 8, 11]

j=1 vet[1] > vet[2] : NO è lascia il vettore invariato

Notiamo che in questo caso non solo i primi due elementi sono già nella loro posizione definitiva, come richiesto, ma anche gli altri. Nelle successive iterazioni non ci saranno altri scambi.

Bubble Sort

(17)

Bubble sort sugli elementi di un array A di dimensione n

– Basato su una logica incrementale: portare nella posizione k il più piccolo degli elementi del sottoarray A[k…n-1] (con k da 0 a n-1)

– algoritmo efficiente per ordinare piccoli insieme di elementi

• Caso peggiore: l’array ordinato in modo decrescente

• Caso migliore: l’array ordinato in modo crescente

for k from 0 to n-2

for j from n-2 to k by -1:

if A[j] > A[j+1]:

A[j] « A[j+1] # scambia

Bubble Sort

esercizio20.1.cpp

(18)

Selection Sort

(19)

basso

Tecnica di ordinamento con individuazione della posizione del minimo e scambio finale

– Supponiamo che le prime k carte siano ordinate e nella loro posizione definitiva (totalmente ordinate)

– Scorriamo le carte non ordinate per individuare la posizione della carta più piccola per poi scambiarla con quella di posto k

• dalla carta di posizione k all’ultima mediante confronti si aggiorna la posizione della più piccola

– Ora le prime k+1 carte sono ordinate … itera l’algoritmo

k

tot. ordinati

non ordinati 0

basso basso basso

> > > < <

Selection Sort

(20)

Usa lo stesso ciclo esterno del bubble sort, mentre per portare l’elemento giusto al posto k determina dapprima l’indice

dell’elemento più piccolo tra i numeri di indice da k a N-1 ed in uscita dal ciclo lo scambia con l’elemento in posizione k

for (k=0; k<N;k++) {

//Ciclo Esterno

// PRE: gli elementi da 0 a k-1 sono nella loro posizione definitiva

IndiceMinimo ¬ k ;

for (j=k+1; j< N ; j++)

//Ciclo Interno

if vet[j] < vet[IndiceMinimo]

//se l’elemento di ordine j è più //piccolo di quello di ordine IndiceMinimo, allora

IndiceMinimo ¬j;

Scambia(vet[k], vet[IndiceMinimo

]); // scambia l’elemento di ordine // IndiceMinimo con quello di ordine k in modo che sia // verificata la postcondizione:

//POST: vet[k] è il più piccolo di tutti gli elementi compresi tra k ed N e dunque tutti gli elementi da 0 a k sono nella loro posizione definitiva.

Selection Sort

(21)

k=0

k=1

k=2

10 19 9 30 29 12 18

2

0

10 19 9 30 29 12 18

2

0

10 19 9 30 29 12 18

2

0

10 19 9 30 29 12 18

2

0

10 19 9 30 29

12 18

²

0

9 19 10 30 29 12 18

2

1

9 19 10 30 29 12 18

2

1

9 19 10 30 29 12 18

2

1

9 19 10 30 29 12 18

2

1

9 19 10 30 29 12 18

²

1

9 10 19 30 29 12 18

2 2

10 19 9 30 29 12 18

0 0

9 10 19 30 29 12 18

2 2

9 10 19 30 29 12 18

5 2

9 10 19 30 29

12 18

⁵

2

Selection Sort

(22)

k=3

k=4

k=5

N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2

9 10 12 30 29 19 18

4 3

9 10 12 30 29 19 18

5 3

9 10 12 30 29 19 18

⁶

3

9 10 12 18 30 29 19

⁵

4

9 10 12 18 30 29 19

⁶

4

9 10 12 18 19 29 30

5 5

9 10 12 18 19 29 30

⁶

Selection Sort

(23)

Selection sort sugli elementi di un array A di dimensione n

– Basato su una logica incrementale: portare nella posizione k il più piccolo degli elementi del sottoarray A[k…n-1] (con k da 0 a n-1)

– algoritmo efficiente per ordinare piccoli insieme di elementi

• Caso peggiore: l’array ordinato in modo decrescente

• Caso migliore: l’array ordinato in modo crescente

for k from 0 to n-1:

basso ß k

for j from k+1 to n-1:

if A[j] < A[basso]:

basso ß j

A[k] « A[basso] # scambia

Selection Sort

esercizio20.1.cpp

(24)

1. Velocizzare l’algoritmo di bubble sort introducendo un controllo nel loop interno per registrare se è avvenuto almeno uno

scambio; se non c’è stato nessuno scambio significa che il vettore è già ordinato ed il loop esterno può essere interrotto.

2. Adoperare la tecnica del bubble sort per:

a) trasformare un vettore di numeri in uno contenente prima i pari seguiti da tutti i dispari

b) trasformare un vettore di numeri in uno contenente all’inizio tutti gli zeri, seguiti da tutti i negativi e terminante con i numeri positivi