Algoritmi di Ordinamento, Silvia Rossi « Programmazione I (SMF) « Scienze Matematiche Fisiche e Naturali

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.

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.

Ordinamento di Stringhe

Ordinamento

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.

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

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

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

Bubble Sort

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

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

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.

Si veda l’ esercizio 20.1

Selection Sort

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.

Selection Sort

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.

Si veda l’ esercizio 20.1

Esercizi

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.
Adoperare la tecnica del bubble sort per:

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

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