Corso di Laurea Triennale in Ingegneria Gestionale
Corso di Fondamenti di Informatica
A. A. 2006 - 2007
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