Ritorna alla home




ORDINAMENTO

Gli algoritmi di ordinamento vengono utilizzati per ordinare un insieme di elementi. L'ordinamento di un insieme puo' avvenire in vari modi a seconda delle nostre esigenze. La scelta dell'algoritmo di ordinamento deve essere effettuata sulla base della valutazione della complessita' computazionale

Esaminiamo i seguenti algoritmi di ordinamento:

----Ritorna----
ORDINAMENTO PER SELEZIONE
Strategia risolutiva
L'algoritmo seleziona l'elemento piu' piccolo e lo inserisce nella posizione corretta. In particolare la prima volta seleziona l'elemento piu' piccolo e lo scambia con quello che occupa la prima posizione, la seconda volta ripete la stessa operazione prendendo in considerazione tutto l'insieme tranne il primo elemento e cosi' via fino a che l'insieme considerato si riduce all'ultimo elemento.
Flow-chart
Di seguito viene illustrato il flow chart dell'ordinamento per selezione :
Ritorna alla home

Complessita' computazionale
La complessita' computazionale dell'algoritmo per selezione e' la seguente :
Al primo passo si effettuano N-1 confronti, al secondo passo N-2 e cosi' via:
(N-1)+(N-2)+...+1 = (N-1+1)(N-1)/2 = N(N-1)/2
Pertanto il metodo di selezione presenta un numero di confronti proporzionale a N2.
La prestazione del metodo rispetto al numero di confronti non e' influenzata dalla configurazione iniziale dei dati.
Nota:
Nel caso migliore verranno effettuati 0 spostamenti;
nel caso peggiore verranno effettuati N-1 spostamenti.
Codifica in C++
Di seguito e riportata la codifica in linguaggio C++ dell'algoritmo di ordinamento per selezione :

void OrdinamentoPerSelezione(int vetpar[10],int dimlogpar)
{
int i=0,j,k;
do
{
k=i;
j=i+1;
do
{
if(vetpar[k]>vetpar[j]) k=j;
j++;
}
while(j<dimlogpar);
if(i!=k)
{
int app=vetpar[i];
vetpar[i]=vetpar[k];
vetpar[k]=app;
}
i++;
}
while(i<dimlogpar-1);
}
----Ritorna----
ORDINAMENTO PER INSERZIONE
Strategia risolutiva
Quest'algoritmo inserisce l'elemento nella giusta posizione e per questo motivo deve preliminarmente determinare il posto dove deve essere copiato. Per trovare la giusta posizione, l'elemento selezionato viene confrontato con quelli che lo precedono mediante una scansione all'indietro. Ovviamente la prima volta confronta il secondo con il precedente, la seconda volta confronta il terzo con i precedenti e cosi' via.
Flow-chart
Di seguito viene illustrato il flow chart dell'ordinamento per inserzione :
Ritorna alla home

Complessita' computazionale
La complessita' computazionale dell'algoritmo per inserzione e' la seguente :
L'ordinamento per inserzione è un buon metodo a condizione che i dati siano complessivamente quasi ordinati. Il caso peggiore si ha quando le chiavi risultano ordinate in senso contrario a quello desiderato, poichè ogni volta che si inserisce una chiave devono essere spostate tutte le chiavi già ordinate in precedenza. Nel caso peggiore si ha che si effettua un confronto al primo passo, due confronti al secondo passo, e così via fino a fare n-1 confronti all' ultimo passo, quindi:
1+2+...+(N-2)+(N-1) = (N-1+1)(N-1)/2 = N(N-1)/2
Questa valutazione è valida anche nella media dei casi.
Codifica in C++
Di seguito e riportata la codifica in linguaggio C++ dell'algoritmo di ordinamento per inserzione :

void OrdinamentoPerInserzione(int vetpar[10],int dimlogpar)
{
int j,k,i;
j=1;
do
{
i=j-1;
k=vetpar[j];
while(i>=0 && k<vetpar[i])
{
vetpar[i+1]=vetpar[i];
i--;
}
vetpar[i+1]=k;
j++;
}
while(j<dimlogpar);
}
----Ritorna----
ORDINAMENTO PER AFFIORAMENTO
Strategia risolutiva
Questo metodo, usualmente denominato "Bubble Sort", ad ogni passo colloca l'elemento più grande nella sua posizione finale. In genere potranno essere più di uno gli elementi che vanno al giusto posto. Si fa uso di una variabile "lim" che registra la posizione dell'ultimo scambio al passo precedente e di una variabile "flag" per controllare se ci sono stati scambi all'ultimo passo.
Nel caso in cui non vengono effettuati scambi in un passo, l'algoritmo termina perchè l'insieme è ordinato. Ad ogni passo, viene preso in esame l'insieme fino alla posizione "lim". In sintesi, l'algoritmo migliora quello a cicli fissi (due cicli annidati) attivando una flag per la segnalazione dell'insieme già ordinato e di una variabile "lim" che riduce l'insieme da prendere in considerazione ad ogni passo.
Flow-chart
Di seguito viene illustrato il flow chart dell'ordinamento per affioramento :

Ritorna alla home

Complessita' computazionale
La complessita' computazionale dell'algoritmo per affioramento e' la seguente :
Al primo passo si effettuano N-1 confronti, al secondo passo N-2 e cosi' via:
(N-1)+(N-2)+...+1 = (N-1+1)(N-1)/2 = N(N-1)/2
Pertanto il metodo di affioramento presenta un numero di confronti proporzionale a N2.
La prestazione del metodo rispetto al numero di confronti e' influenzata dalla configurazione iniziale dei dati. Se questi sono parzialmente ordinati, il numero di passi dell'algoritmo puo' essere notevolmente minore del numero massimo.
Codifica in C++
Di seguito e riportata la codifica in linguaggio C++ dell'algoritmo di ordinamento per affioramento :

void OrdinamentoPerAffioramento(int vetpar[10],int dimlogpar)
{
int lim=dimlogpar,flag=0,j=0;
do
{
do
{
if(vetpar[j]>vetpar[j+1])
{
int app=vetpar[j];
vetpar[j]=vetpar[j+1];
vetpar[j+1]=app;
flag=j;
}
j++;
}
while(!(j>lim-2));
if(flag!=0) lim=flag;
}
while(flag!=0);
}
----Ritorna----
ALGORITMO DI PARTIZIONE
Strategia risolutiva
Il seguente algoritmo di partizione posiziona gli elementi più piccoli di un separatore dell’insieme da partizionare alla sua sinistra e gli elementi più grandi alla sua destra. Come separatore (perno) si conviene di scegliere il primo elemento dell’insieme. La procedura di partizione viene realizzata confrontando il perno con tutte le altre chiavi presenti nell’insieme. I due cursori “i” e “j” puntano rispettivamente al lato sinistro e destro dell’insieme da partizionare. Lo spostamento dei due cursori avviene in senso contrario, pertanto “j” verrà decrementato mentre “i” verrà incrementato; quando i due cursori si incontrano il processo di partizione termina.
Flow-chart
Di seguito viene illustrato il flow chart dell'algoritmo di partizione:

Ritorna alla home

Codifica in C++
Di seguito e riportata la codifica in linguaggio C++ dell'algoritmo di partizione :

void AlgoritmoDiPartizione(int vetpar[10],int dimlogpar)
{
int app;
int i=0;
int j=dimlogpar;
while(i<j);
{
do
{
j--;
}
while(vetpar[i]<vetpar[j] && i<j);
if(i<j)
{
int app=vetpar[i];
vetpar[i]=vetpar[j];
vetpar[j]=app;
do
{
i++;
}
while(vetpar[i]<vetpar[j] && i<j);
}
if(i<j)
{
int app=vetpar[i];
vetpar[i]=vetpar[j];
vetpar[j]=app;
}
}
}
----Ritorna----
ORDINAMENTO CON QUICK-SORT
Strategia risolutiva
L'ordinamento quick-sort e' basato sulla chiamata ricorsiva dell'algoritmo di partizione.
QuickSort.
1) Se inf = sup stop;
2) Esegui algoritmo di partizione sul vettore delimitato da inf e da sup determinando la posizione i dell'elemento separatore;
3) Se inf < i esegui il QuickSort sul vettore delimitato da inf e i-1;
4) Se i < sup esegui il QuickSort sul vettore delimitato da i+1 e da sup.
Pseudocodifica
Di seguito e' riportata la pseudocodifica dell'algoritmo di ordinamento quick sort :

Procedura QuickSort(vet:intero,inf:intero,sup:intero)
INIZIO
MENTRE(inf!=sup)
AlgoritmoDiPartizione(vet,inf,sup);
SE(inf < perno) QuickSort(vet,inf,perno-1);
SE(perno < sup) QuickSort(vet,perno+1,sup);
FINE MENTRE
FINE
Codifica in C++
Di seguito è riportata la codifica in linguaggio C++ dell'algoritmo di quick-sort :

void QuickSort(int vetpar[10], int infpar, int suppar)
{
if(infpar<suppar)
{
int j = AlgoritmoDiPartizione(vetpar,infpar,suppar);
QuickSort(vetpar,infpar,j-1);
QuickSort(vetpar,j+1,suppar);
}
}

Codifica completa:

#include<iostream>
#include<cstdlib>
using namespace std;
int vet[10],dimlog,inf,sup;

//Prototipi
int OttieniDim();
void CaricaVet(int vetpar[10],int dimlogpar);
void StampaVet(int vetpar[10],int dimlogpar);
int AlgoritmoDiPartizione(int vetpar[10],int infpar,int suppar);
void QuickSort(int vetpar[10],int infpar,int suppar);

main()
{
cout<<"Quanti elementi vuoi inserire? ";
dimlog=OttieniDim();
CaricaVet(vet,dimlog);
StampaVet(vet,dimlog);
cout<<endl;
cout<<"Inserisci inf: "; cin>>inf; cout<<"Inserisci sup: "; cin>>sup; QuickSort(vet,inf,sup); cout<<"Dopo l'ordinamento: "<<endl;
StampaVet(vet,dimlog);
cout<<endl;
system("pause");
}

int OttieniDim()
{
int dim;
do
{
cin>>dim;
if(!(dim>0 && dim<=10)) cout<<"Hai sbagliato! Riprova! ";
}
while(!(dim>0 && dim<=10));
return dim;
}

void CaricaVet(int vetpar[10],int dimlogpar)
{
for(int i=0;i<dimlogpar;i++)
{
cout<<"Inserire un numero: ";
cin>>vetpar[i];
}
}

void StampaVet(int vetpar[10],int dimlogpar)
{
for(int i=0;i<dimlogpar;i++) cout<<vetpar[i]<<" ";
}

int AlgoritmoDiPartizione(int vetpar[10],int infpar,int suppar)
{
int pivot=vetpar[infpar];
while(infpar<suppar)
{
while(vetpar[infpar]<pivot)
infpar++;
while(vetpar[suppar]>pivot)
suppar--;
if(vetpar[infpar]==vetpar[suppar])
infpar++;
else if(infpar<suppar)
{
int app = vetpar[infpar];
vetpar[infpar]=vetpar[suppar];
vetpar[suppar]=app;
}
}
return suppar;
}

void QuickSort(int vetpar[10], int infpar, int suppar)
{
if(infpar<suppar)
{
int j = AlgoritmoDiPartizione(vetpar,infpar,suppar);
QuickSort(vetpar,infpar,j-1);
QuickSort(vetpar,j+1,suppar);
}
}

Complessita' computazionale
La complessita' computazionale dell'algoritmo quick-sort e' la seguente :
Il caso migliore nel quick-sort si ha quando la disposizione dei dati è tale che ad ogni passo il separaratore viene collocato alla metà esatta dell'insieme che si considera.
Supponiamo N (dimensione dell'insieme) uguale a 2h-1 nel caso medio il numero di confronti sarà proporzionale a (h-1)*N.
Il caso peggiore si ha quando gli elementi sono già ordinati. In questo caso il numero di confronti sarà proporzionale a N2.
----Ritorna----
ALGORITMO DI FUSIONE
Strategia risolutiva
Il seguente algoritmo di fusione genera un unico insieme ordinato a partire da due insiemi ordinati. Dati due vettori ordinati "vet1" e "vet2" di dimensione rispettivamente N e M si vuole ottenere un terzo vettore "vet3" ordinato contenente gli elementi di vet1 e vet2. "i" è il cursore che scorre vet1, "j" scorre vet2, "k" scorre vet3. Si confronta il valore di vet[i] con il valore vet[j] e il più piccolo "cade" in vet3, si incrementa il cursore del vettore il cui elemento è caduto in vet3 e k. I suddetti confronti terminano se i e/o j raggiungono la dimensione logica. Quando uno dei due vettori vet1 e vet2 è stato scandito completamente, i restanti elementi dell'altro vettore, se esistono, vengono copiati in vet3.
Flow-chart
Di seguito viene illustrato il flow chart dell'algoritmo di fusione:

Ritorna alla home

Codifica in C++
Di seguito e riportata la codifica in linguaggio C++ dell'algoritmo di fusione :

void AlgoritmoDiFusione(int vet1par[10],int vet2par[10],int dimlog1par,int dimlog2par)
{
int vet3[dimlog1par+dimlog2par];
int i=0,j=0,k=0;
do
{
if(vet1par[i]<=vet2par[j])
{
vet3[k]=vet1par[i];
k++;
i++;
}
else
{
vet3[k]=vet2par[j];
k++;
j++;
}
}
while(i<dimlog1par && j<dimlog2par);
if(i<=dimlog1par)
{
while(i<dimlog1par)
{
vet3[k]=vet1par[i];
k++;
i++;
}
}
if(j<=dimlog2par)
{
while(j<dimlog2par)
{
vet3[k]=vet2par[j];
k++;
j++;
}
}
}
ORDINAMENTO CON SORT-MERGE
Strategia risolutiva
L'ordinamento sort-merge e' basato sul richiamo ricorsivo dell'algoritmo di fusione e sul "divide et impera". Si suddividono gli elementi del vettore in coppie costituite da elementi consecutivi e mediante la fusione si ordinano, successivamente si procede alla fusione della prima coppia con la seconda e così via ottenendo quadruple di elementi ordinati. Si ripete il procedimento fino ad ottenere un unico insieme ordinato.
Pseudocodifica
Di seguito e' riportata la pseudocodifica dell'algoritmo di ordinamento sort-merge:

Procedura SortMerge(vet:intero,inf:intero,sup:intero)
INIZIO
MENTRE(inf!=sup)
centro=(inf+sup)/2;
SortMerge(vet,inf,centro);
SortMerge(vet,centro+1,sup);
AlgoritmoDiFusione(vet,inf,centro,centro+1,sup);
FINE MENTRE
FINE
Codifica in C++
Di seguito è riportata la codifica in linguaggio C++ dell'algoritmo di sort-merge :

void SortMerge(int vetpar[10], int infpar, int suppar)
{
if(infpar<suppar)
{
int centro = (infpar+suppar)/2;
SortMerge(vetpar,infpar,centro);
SortMerge(vetpar,centro+1,suppar);
AlgoritmoDiFusione(vetpar,infpar,centro,suppar);
}
}

Codifica completa:

#include<iostream>
#include<cstdlib>
using namespace std;
int vet[10],dimlog;

//Prototipi
int OttieniDim();
void CaricaVet(int vetpar[10],int dimlogpar);
void StampaVet(int vetpar[10],int dimlogpar);
void SortMerge(int vetpar[10],int infpar,int suppar);
void AlgoritmoDiFusione(int vetpar[10],int infpar,int centropar,int suppar);

main()
{
cout<<"Quanti elementi vuoi inserire? ";
dimlog=OttieniDim();
CaricaVet(vet,dimlog);
StampaVet(vet,dimlog);
cout<<endl;
SortMerge(vet,0,dimlog-1);
cout<<"Dopo l'ordinamento: "<<endl;
StampaVet(vet,dimlog);
cout<<endl;
system("pause");
}

int OttieniDim()
{
int dim;
do
{
cin>>dim;
if(!(dim>0 && dim<=10)) cout<<"Hai sbagliato! Riprova! ";
}
while(!(dim>0 && dim<=10));
return dim;
}

void CaricaVet(int vetpar[10],int dimlogpar)
{
for(int i=0;i<dimlogpar;i++)
{
cout<<"Inserire un numero: ";
cin>>vetpar[i];
}
}

void StampaVet(int vetpar[10],int dimlogpar)
{
for(int i=0;i<dimlogpar;i++) cout<<vetpar[i]<<" ";
}

void AlgoritmoDiFusione(int vetpar[10],int infpar,int centropar,int suppar)
{
int i,j,k;
int vet2[8];
i=infpar;
j=centropar+1;
k=0;
while((i<=centropar)&&(j<=suppar))
{
if (vetpar[i]<=vetpar[j])
{
vet2[k]=vetpar[i];
i++;
}
else
{
vet2[k]=vetpar[j];
j++;
}
k++;
}
while (i<=centropar)
{
vet2[k]=vetpar[i];
i++;
k++;
}
while (j<=suppar)
{
vet2[k]=vetpar[j];
j++;
k++;
}
for (k=infpar;k<=suppar;k++)
{
vetpar[k]=vet2[k-infpar];
}
}
void SortMerge(int vetpar[10], int infpar, int suppar)
{
if(infpar<suppar)
{
int centro = (infpar+suppar)/2;
SortMerge(vetpar,infpar,centro);
SortMerge(vetpar,centro+1,suppar);
AlgoritmoDiFusione(vetpar,infpar,centro,suppar);
}
}

Complessita' computazionale
La complessita' computazionale dell'algoritmo sort-merge e' la stessa in tutti e tre i casi. Supponiamo N (dimensione dell'insieme) uguale a 2h-1 il numero di confronti sarà proporzionale a (h-1)*N.
----Ritorna----