Corso di Laurea Triennale in Ingegneria Gestionale
Corso di Fondamenti di Informatica
A. A. 2004 - 2005
Gli Algoritmi di ordinamento
1
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Gli Algoritmi di Ordinamento - Generalità
L’ordinamento è il processo che permette di ottenere,a
partire da un insieme di dati omogenei, un insieme
ordinato, secondo un ordine crescente o decrescente,.
Assunzione :
 consideriamo solo l’ordinamento di vettori contenenti
numeri o lettere;
I metodi considerati per descrivere l’ordinamento di un
vettore sono :
 Ordinamento per selezione
 Ordinamento per scambio
2
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Ordinamento per
selezione/Selection-sort
Obiettivo:ottenere un insieme di elementi,ordinato in maniera decrescente
L’ordinamento per Selezione seleziona l’elemento con
valore maggiore e lo scambia con il primo elemento del
vettore. Tra gli N-1 elementi rimanenti viene poi
ricercato nuovamente quello maggiore e scambiato con il
secondo e così via fino all’ultimo elemento.
3
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Selection Sort – L’Algoritmo
I passi da seguire sono i seguenti :
1) Posizionamento sul primo elemento dell’array
2) Ricerca dell’elemento più grande e scambio con il primo elemento
dell’array
3) Posizionamento sul secondo elemento dell’array
4) Ricerca dell’elemento più grande tra gli N-1 elementi rimasti e scambio con
il secondo elemento dell’array
5) Posizionamento sul terzo elemento dell’array
6) Ricerca dell’elemento più grande tra gli N-2 elementi rimasti e scambio con
il terzo elemento dell’array
7) Tale procedimento viene ripetuto N-1 volte
Osservazione : Per implementare l’Algoritmo abbiamo bisogno di 2 indici :
 Uno che tiene conto della posizione in cui si trova l’elemento da ordinare
( primo, secondo, terzo, … )
 Uno che permette di scorrere l’array alla ricerca del valore maggiore
4
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
Ordinamento per selezione
DEE - Politecnico di Bari
Esempio
vettore A
b
d
a
c
Passo 1
d
b
a
c
Passo 2
d
c
a
b
Passo 3
d
c
b
a
5
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Selection-sort il codice 1/3
/* Algoritmo di Selection Sort */
#include <stdio.h>
// definisco la dimensione massima del vettore
#define MAXDIM 20
main()
{
// La dichiarazione delle variabili
int i,j,N,temp;
int V[MAXDIM];
// Inserimento della dimensione del vettore con controllo che sia minore o uguale
//alla dimensione massima
do{
printf("\n Inserire la dimensione del vettore non superiore a %d\n",MAXDIM);
// inserimento del valore da tastiera
scanf("%d",&N);
}while(N>MAXDIM);
6
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Selection-sort il codice 2/3
for (i=0;i<N;i++) // inserimento del vettore
{
printf("Inserire l'elemento %d : ",i+1);
scanf("%d",&V[i]);
}
for (i=0;i<N-1;i++)
{
//Blocco di Istruzioni - S1
j = i+1;
do{
if ( V[ i ] <[ j ] )
{ // effettuare scambio degli elementi
temp = V[ i ];
V[ i ] = V[ j ];
V[ j ] = temp;
}
j = j + 1;
}while( j < N );
}
7
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Selection-sort il codice 3/3
// visualizzazione del vettore ordinato mediante l'algoritmo
printf("Il vettore ordinato e\' il seguente : \n");
for (i=0;i<N;i++)
printf("%d ",V[i]);
printf("\n");
} // chiude il main
8
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Ordinamento per scambio
Si scandisce tutto l’insieme, se due elementi vengono
trovati fuori posto si scambiano tra loro. Questo
procedimento viene ripetuto fino a quando non si hanno
più cambiamenti.
 Bubble Sort – vengono effettuati confronti ripetuti e, se
necessario, scambi di elementi adiacenti. Un vettore di N
elementi viene letto per intero N – 1 volte sempre
partendo dall’ultimo elemento.
9
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Ordinamento per scambio/Bubble-Sort
Osservazione : Per implementare l’Algoritmo abbiamo bisogno di 2
indici :
 Uno che tiene conto della posizione in cui si
trova l’elemento già ordinato( fino al primo, fino
al secondo, fino al terzo, … )
 Uno che permette di scorrere l’array alla ricerca
del valore minimo
vettore iniziale
10
a b c d
Passo 1
da b c
Passo 2
dc a b
Passo 3
d c b a
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort codice 1/3
#include <stdio.h>
// definisco la dimensione massima del vettore
#define MAXDIM 20
main()
{
// La dichiarazione delle variabili
int i,j,N,temp;
int V[MAXDIM];
// Inserimento della dimensione del vettore con
//controllo che sia minore o uguale alla dimensione
//massima
do{
printf("\n Inserire la dimensione del vettore non superiore a %d\n",MAXDIM);
// inserimento del valore da tastiera
scanf("%d",&N);
}while(N>MAXDIM);
11
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort codice 2/3
for (i=0;i<N;i++) // inserimento del vettore
{
printf("Inserire l'elemento %d : ",i+1);
scanf("%d",&V[i]);
}
for (i=0;i<N-1;i++)
{
j = N -1; //Posizionamento ad ogni step i sull’ultimo elemento
do{
if ( V[ j-1 ] <V[ j ] )
{ // effettuare scambio degli elementi adiacenti
temp = V[ j-1 ];
V[ j-1 ] = V[ j ];
V[ j ] = temp;
}
j = j - 1;
}while( j > i );
}
12
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort codice 3/3
// visualizzazione del vettore ordinato mediante l'algoritmo
printf("Il vettore ordinato e\' il seguente : \n");
for (i=0;i<N;i++)
printf("%d ",V[i]);
printf("\n");
} // chiude il main
13
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort versione ottimizzata
Una versione ottimizzata dell’algoritmo, termina se non avvengono
scambi anche se vengono comunque effettuati i confronti per ogni
esecuzione del ciclo più interno.
Ossia il ciclo più interno di confronto degli elementi adiacenti viene
eseguito per intero, ma se in tale ciclo non avvengono scambi, ossia
il vettore è già ordinato, il programma termina.
Osservazione : Per tale implementazione abbiamo
bisogno di :
 Una variabile del tipo vero – falso che indichi se sono avvenuti
scambi nel ciclo più interno
 Modificare la condizione del ciclo più esterno perché dobbiamo
chiedere che si esca dal programma dopo N -1 passi oppure se non
si sono effettuati scambi
14
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort versione ottimizzata1/2
#include <stdio.h>
// definisco la dimensione massima del vettore
#define MAXDIM 20
main()
{
// La dichiarazione delle variabili
int i,j,N,temp, scambio;
int V[MAXDIM];
// Inserimento della dimensione del vettore con
//controllo che sia minore o uguale alla dimensione
//massima
do{
printf("\n Inserire la dimensione del vettore non superiore a %d\n",MAXDIM);
// inserimento del valore da tastiera
scanf("%d",&N);
}while(N>MAXDIM);
15
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort versione ottimizzata 2/3
for (i=0;i<N;i++)
{
printf("Inserire l'elemento %d : ",i+1);
scanf("%d",&V[i]);
}
scambio = 1;
for (i=0;i<N-1 && scambio ==1;i++)
{
j = N -1; // ordinamento
scambio = 0;
do{
if ( V[ j-1 ] < V[ j ] )
{ // effettuare scambio degli elementi adiacenti
temp = V[ j-1 ];
V[ j-1 ] = V[ j ];
V[ j ] = temp;
scambio =1;}
j = j - 1;
}while( j > i );
}
16
Algoritmi di ordinamento
A.Pinto
Sistemi Informativi
DEE - Politecnico di Bari
Bubble-sort versione ottimizzata 3/3
// visualizzazione del vettore ordinato
printf("Il vettore ordinato e\' il seguente : \n");
for (i=0;i<N;i++)
printf("%d ",V[i]);
printf("\n");
} // chiude il main
17
Algoritmi di ordinamento
A.Pinto