ORDINAMENTI

VARI TIPI DI ORDINAMENTI VETTORIALI

Un algoritmo di ordinamento ((EN) sorting algorithm) è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente.

Esistono vari tipi di algoritmi di ordinamento.


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 nel dettagli l' algoritmo : dato un vettore con n elementi, per ogni iterazione il primo elemento viene confrontato con il secondo, e se risulta maggiore, viene scambiato. La stessa cosa avviene tra il secondo ed il terzo elemento e cosi via fino alla fine del vettore. Dopo n-1 iterazione il nostro vettore risulterá ordinato.

Ecco l' implementazione in java dell' algoritmo :

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-esima posizione.


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.



Merge sort

Il Merge sort e' un algoritmo di ordinamento ricorsivo; Alla base di questo metodo c'e' il procedimento Divide et Impera, che consiste nella divisione di un problema in problemi via via più piccoli. Il merge sort opera quindi dividendo l'insieme da ordinare in 2 meta'. Una volta ottenute le meta' si provvede alla loro fusione ordinandole.

Il vettore viene diviso in due meta', se e' formato da un numero pari di elementi la prima parte ha un elemento in piu'. Si ordinano le parti separatamente e per unirle l'algoritmo estrae il minimo dalle due parti e li fonde in un'unica sequenza.

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.

Vediamo nel dettaglio : dato un vettore di n elementi, vengono effettuate n-1 iterazioni ed a ogni iterazione i, si scandisce una porzione del vettore cha va da i-1 a 0 trovando la posizione giusta dell'i-esimo elemento, tramite una serie di scambi. Quindi procedendo in questo modo la porzione del vettore che va da i-1 a 0 risulterá sempre ordinata e alla fine di n iterazioni tutto il vettore risulterá ordinato.


Realizzato da ragazzi della 4°A O.S.A del liceo Leonardo Da Vinci.

Comment Stream

2 years ago
0

good job!