Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Silvia Rossi » 20.Algoritmi di Ordinamento


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


Ordinamento


Ordinamento


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


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


Bubble Sort


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


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


Selection Sort


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

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

I materiali di supporto della lezione

Esercizo 20.1

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion