[Pillola][Tutorial] Principali algoritmi di ordinamento in c++
Sto preparando una materia su vari algoritmi e mi stavo scrivendo una implementazione c++ dei più noti algoritmi di ordinamento... ottimo argomento per risollevare un pochino la sezione, perciò ho pensato di scrivere qui il tutto :)
Userò per semplicità un array di int, gli algoritmi, con opportune modifiche, sono però utilizzabili con qualsiasi array ordinabile in maniera crescente, cioè con elementi su cui si può distinguere un maggiore da un minore, siano essi numeri, lettere o oggetti.
Per iniziare scriviamo un semplice programmino che useremo per i test che chiede di inserire 10 numeri interi da memorizzare sull'array:
Codice:
#include <iostream>
#define SIZE 10
using namespace std;
int main()
{
int array[SIZE];
int A[SIZE];
int c=0;
cout << "- ALGORITMI -\n";
cout << "Inserire 10 valori interi a piacere:\n";
for (c=0; c<SIZE; c++)
{
cout<<"Valore "; cout<<c; cout<<": ";
cin >> array[c];
}
cout << "\n\nArray di partenza:\n";
for (c=0; c<SIZE; c++) {A[c]=array[c]; cout<<A[c]; cout<<" ";}
return 0;
}
"array" servirà a conservare il nostro array di partenza, mentre useremo A per gli ordinamenti, ripristinandolo dopo ogni chiamata.
Insertion sort
L'insertion sort è uno degli algoritmi più facili da implementare, poco codice leggibile e la qualità di ordinare in loco (cioè senza far uso di array di appoggio, ma solo di una variabile temporanea per gli scambi)
Codice:
void insertionSort( int* A)
{
int key, i;
for (int j=1; j<SIZE; j++)
{
key=A[j];
i=j-1;
//si inserisce A[j] nella sequenza ordinata A[0...j-1]
while(i>=0&&A[i]>key)
{
A[i+1]=A[i];
i--;
}
A[i+1]=key;
}
}
l'algoritmo lavora dando per già ordinata una sequenza variabile A[0..j-1] dell'array, questa sequenza al primo ciclo corrisponde al solo primo elemento dell'array perchè j sarà uguale a 1, un solo elemento è sicuramente ordinato, proseguendo analizzerà ciclo dopo ciclio l'elemento A[j] (cioè dal secondo elemento dell'array fino alla fine) copiandolo su key e poi facendolo "scalare" di posto fino a raggiungere la giusta posizione nella sequenza già ordinata che perciò crescerà di uno ad ogni ciclo, fino ad ottenere l'array completo.
esempio:
6 4 5 8 - sequenza ordinata [6], key=4
4 6 5 8 - sequenza ordinata [4 6], key=5
4 5 6 8 - sequenza ordinata [4 5 6], key=8
4 5 6 8 - sequenza ordinata [4 5 6 8], fine dell'ordinamento
Analisi di insertion sort
insertion sort presenta due cicli concatenati, in questa versione un for e un while interno, il for viene eseguito SIZE-1 volte, mentre il while viene eseguito una volta nel caso migliore (la key esaminata è già al suo posto) o tante volte quanta è la grandezza della sequenza ordinata in quello peggiore.
Esso ha perciò una complessità lineare (n) nel caso di un array già ordinato e una quadratica (n^2) nel caso che l'array sia completamente disordinato (ordinato in maniera decrescente).
adesso esco.. buon sabato sera a tutti .-. continuerò presto con merge sort, heap sort e altri :)
ah, ecco il main con la chiamata ad insertion sort, dichiarate sopra la funzione o mettetelo alla fine del file, o comunque sotto insertionsort
Codice:
int main()
{
int array[SIZE];
int A[SIZE];
int c=0;
cout << "- ALGORITMI -\n";
cout << "Inserire 10 valori interi a piacere:\n";
for (c=0; c<SIZE; c++)
{
cout<<"Valore "; cout<<c; cout<<": ";
cin >> array[c];
}
cout << "Insertion Sort\n";
cout << "\n\nArray di partenza:\n";
for (c=0; c<SIZE; c++) {A[c]=array[c]; cout<<A[c]; cout<<" ";}
insertionSort(A);
cout << "\nArray ordinato:\n";
for (c=0; c<SIZE; c++) {cout<<A[c]; cout<<" ";}
cout << "\n\n";
return 0;
}
Merge sort
Come vedremo, il merge sort è un algoritmo ricorsivo, e fa uso della tecnica Divide-et-Impera (Dividi e conquista). Tutti gli algoritmi che ne fanno uso risolvono il loro compito più o meno in questo modo:
- il problema iniziale viene diviso in due sottoproblemi
- entrambi i sottoproblemi sono risolti usando nuovamente l'algoritmo su di loro (ricorsione)
- se il problema da risolvere è abbastanza piccolo viene data una soluzione diretta
Nel caso di merge sort questo procedimento genera perciò una suddivisione dell'array in due sotto array e dei due sotto array in quattro, e così via fino a giungere a sotto array di un elemento ciascuno che vengono ritornati come risultato alle funzioni chiamanti, esse uniscono le soluzioni con una procedura "merge" di appoggio e ritornano il tutto alle loro funzioni chiamanti, che a loro volta usano il merge, il tutto fino ad arrivare alla prima funzione che unisce tra loro le soluzioni e genera l'array ordinato.
Questo procedimento può apparire a prima vista lento o disordinato, esso è invece piuttosto efficace, anche se sia la ricorsione che la procedura merge non ordinano in loco, relegando perciò l'utilizzo di merge sort esclusivamente ad array piccoli.
Codice:
void mergesort(int* A, int l, int r) {
if (l<r)
{
int c = (l+r)/2;
mergesort(A, l, c);
mergesort(A, c+1, r);
merge(A, l, c, r);
}
}
//merge verrà usata esclusivamente da mergesort
void merge(int* A, int l, int c, int r) {
static int aux[SIZE];
int i,j;
for (i = c+1; i > l; i--) aux[i-1] = A[i-1];
for (j = c; j < r; j++) aux[r+c-j] = A[j+1];
for (int k = l; k <= r; k++)
if (aux[j] < aux[i]) A[k] = aux[j--];
else A[k] = aux[i++];
}
merge prende in input l'array e tre indici che indicano inizio e fine dei due sottoarray da unire, i sottoarray sono ordinati tra loro perciò per unirli basta confrontare due elementi, scegliere il minore e copiarlo, poi confrontare l'elemento rimasto da prima con il successivo dell'altro array, scegliere il minore e così via fino ad esaurire uno dei due array, i restanti elementi dell'altro vengono poi copiati in coda per ottenere infine l'unico array ordinato.
Analisi del merge sort
Essendo questo un algoritmo divide-et-impera possiamo fare l'analisi spezzandolo in tre "sezioni":
Divide il passo di divisione non fa altro che calcolare l'indice di mezzo dell'array, il tempo di esecuzione di esso è perciò costante D(n)= 1.
Impera si risolveranno ricorsivamente due sottoproblemi di grandezza n/2, il tempo di esecuzione sarà 2T(n/2).
Combina la procedura merge su un sottoarray di n elementi impiega un tempo lineare, per cui C(n)= n
avremo perciò:
T(n) = 1 con n=1
T(n) = 2T(n/2)+ n con n>1
2T(n/2)+ n ha infine complessità n*lg n come si evince dall'albero di ricorsione:
Codice:
________n_______________= n
_____/_____\
__n/2_______n/2_________= n
__/_\________/_\
_n/4_n/4___n/4_n/4______= n
___...________...___tot = n (log n)
aggiungiamo la chiamata a mergesort passando come l 0 e come r SIZE-1. Il nostro main diventerà perciò così:
Codice:
int main()
{
int array[SIZE];
int A[SIZE];
int c=0;
cout << "- ALGORITMI -\n";
cout << "Inserire 10 valori interi a piacere:\n";
for (c=0; c<SIZE; c++)
{
cout<<"Valore "; cout<<c; cout<<": ";
cin >> array[c];
}
cout << "Insertion Sort\n";
cout << "\n\nArray di partenza:\n";
for (c=0; c<SIZE; c++) {A[c]=array[c]; cout<<A[c]; cout<<" ";}
insertionSort(A);
cout << "\nArray ordinato:\n";
for (c=0; c<SIZE; c++) {cout<<A[c]; cout<<" ";}
cout << "\n\nArray di partenza:\n";
for (c=0; c<SIZE; c++) {A[c]=array[c]; cout<<A[c]; cout<<" ";}
mergesort(A,0,SIZE-1);
cout << "\nArray ordinato:\n";
for (c=0; c<SIZE; c++) {cout<<A[c]; cout<<" ";}
cout << "\n\n";
return 0;
}
