ORDINAMENTO DI UN VETTORE

COS'E' UN VETTORE?

In informatica un vettore è semplicemente una riga di informazioni (stinghe o numeri). Il numero di elementi memorizzati nel vettore é la dimensione del vettore.

Possiamo considerarlo come una scatola contenente più informazioni dello stesso tipo.

...

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.

... bubble sort

Tra i piú semplici algoritmi di ordinamento abbiamo il BUBBLE SORT, che in italiano significa naturalmente ordinamento a bolle, e già il nome dovrebbe dirci tutto, almeno.

Il meccanismo si basa infatti sull 'idea di far emergere man mano (come bollicine) gli elementi minori all' inizio del vettore mentre contemporaneamente quelli maggiori si posizionano in fondo al vettore.

Vediamo in ambito applicativo come viene usato il bubble sort in java:

public void bubbleSort(int [] array) {

            for(int i = 0; i < array.length; i++) {
            boolean flag = false;
            for(int j = 0; j < array.length-1; j++) { //Se l' elemento j e maggiore del                                                                                                             successivo allora
                                                                                 //scambiamo i valori
                             if(array[j]>array[j+1]) {
                                  int k = array[j];
                                         array[j] = array[j+1];
                                         array[j+1] = k;
                                         flag=true; //Lo setto a true per indicare che é                                                                                                        avvenuto uno scambio

}
}

                          if(!flag) break; //Se flag=false allora vuol dire che nell' ultima iterazione
                                                    //non ci sono stati scambi, quindi il metodo può terminare                                                       //poiché l' array risulta ordinato

... selection sort

Il Selection Sort è un altro algoritmo di ordinamento decisamente semplice ed intuitivo. L' idea di base si fonda nel selezionare ad ogni iterazione l' i-esimo valore piú piccolo, e sostituirlo con quello che in quel momento occupa l' i-esimaposizione.

In altre parole alla prima iterazione verrá selezionato il valore piú piccolo dell' intero vettore e sará scambiato con il vaolore che in quel momento occupa la prima posizione, poi alla seconda iterazione viene selezionato il secondo valore piú piccolo del vettore e sará scambiato con il valore che in quel momento occupa la seconda posizione, e cosí via fino a quando tutti gli elementi del vettore non sono collocati nella loro giusta posizione.



... insertion sort

L' Insertion Sort é un' altro noto e semplice algoritmo di ordinamento che si basa sul concetto di ordinamento per inserzione, simile al modo in cui un essere umano, spesso, ordina un mazzo di carte.



... merge sort

Infine abbiamo Il Merge Sort (ordinamento per fusione) a differenza degli algoritmi visti in precedenza, é un algoritmo di ordinamento piú complesso, ma molto efficiente. Il meccanismo di ordinamento di questo algoritmo consiste nel suddividere un problema complesso in due o piú sotto-problemi piú semplici e poi si ricombinano le soluzioni trovate per ricostruire la soluzione del problema complessivo.

          

Comment Stream