ordinare un vettore; come fare?

                                                                                                     di Luigi Montanino

Il problema dell' ordinamento di un insieme, è un problema molto ricorrente in campo informatico che oltre ad avere un importanza fondamentale in ambito applicativo, rappresenta anche un ottimo strumento didattico. Un algoritmo di ordinamento è appunto un algoritmo capace di ordinare un insieme seguendo una certa relazione d' ordine. Ad esempio si possono trovare facilmente tanti casi di relazioni d’ordine, che spesso esprimiamo con parole come prima/dopo, precede/segue, superiore/inferiore, a monte/a valle, ecc. Di algoritmi di ordinamento ne esistono diversi e di diversi tipi. In questa guida affronteremo gli algoritmi che in gran parte operano esclusivamente sulla base di scambi e confronti, facendo qualche accenno anche alla complessitá di ciascuno. Analizzeremo algoritmi di semplice realizzazione, a scapito della loro complessità computazionale, cioè scarsa efficienza (Bubble Sort, Insertion Sort, Selection Sort), fino ad arrivare a quelli strutturalmente più complessi ma molto efficienti, che fanno uso dell tecnica Divide et Impera, con il meccanismo della ricorsione (Merge Sort)


iniziamo parlando del bubble sort:
Il bubble sort o bubblesort (letteralmente: ordinamento a bolle) è un semplice algoritmo di ordinamento per ordinare array. Non è un algoritmo efficiente: ha una complessità computazionale (misurata in termini di numero di confronti) O(n²); si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità. Dell'algoritmo esistono numerose varianti, per esempio lo shakersort. Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una relazione d'ordine; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di numeri interi.

il codice che lo rappresenta è il seguente :

public void bubbleSort(int[] x) {
int temp = 0;
int j = x.length+1;

while(j<n) {
                for(int i=0; i < j;i++ ) //scambiare il '>' con '<' per ottenere un ordinamento                      decrescente
        {
               temp=x[i];

               x[i]=x[i+1];
               x[i+1]=temp;
       }
     } j++;
   }

}

insertion sort
L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. L'algoritmo utilizza due indici: il primo punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. Se il primo elemento è maggiore del secondo, i due valori vengono scambiati. Poi il primo indice avanza di una posizione e il secondo indice riparte dall'elemento precedente quello puntato dal primo. Se l'elemento puntato dal secondo indice non è maggiore di quello a cui punta il primo indice, il secondo indice indietreggia; e così fa, finché si trova nel punto in cui il valore del primo indice deve essere inserito (da qui insertion). L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

public static void insertionSort(int[] array) {

int j;      //N.B. dichiaro qui j altrimenti non può essere vista dall'ultima istruzione

for (int i = 1; i < array.length; i++) {

       int tmp = array[i]; // l'elemento viene rimosso dalla lista

       for (j =i-1; (j >= 0) && (array[j] > tmp); j--) {

       array[j + 1] = array[j];

}

    array[j + 1] = tmp; // l'elemento rimosso viene reinserito nella giusta posizione // del sottoinsieme ordinato 0..i } }

L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in place ed in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sotto-sequenza ordinata, che occupa le prime posizioni dell'array, e la sotto-sequenza da ordinare, che costituisce la parte restante dell'array. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.I passi sono i seguenti:
si inizializza un puntatore i che va da 1 a n (dove n è la lunghezza dell'array).
Si cerca il più piccolo elemento dell'array
Scambia l'elemento più piccolo con l'elemento alla posizione i
Incrementa l'indice i e si torna al passo uno fino alla fine dell'array.

void selection(double a[], unsigned long N) {

int i, j, min;

double t;

     for (i=0; i < N-1; i++) {

    min = i;

       for (j= i + 1; j < N; j++) {

if (a[j] < a[min]) {

min = j;

}

}

t = a[min];

a[min] = a[i];

a[i] = t;

}

}

infine abbiamo l ordinamento merge sort:
Il merge sort è un algoritmo di ordinamento molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.L'idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del problema in sotto-problemi via via più piccoli.Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato come mostra la figura sottostante

Comment Stream