L’ordinamento, o sorting in inglese, è uno dei concetti più vecchi ma anche più importanti della programmazione in generale. Ovviamente ci sono moltissime tecniche e algoritmi di ordinamento ma grazie a Java non si dovrà implementare niente di tutto ciò, basteranno infatti poche linee  di codice.


1) 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.


2) 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.

3) 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.

4) Il Merge Sort (ordinamento per fusione) a differenza degli algoritmi visti in precedenza, é un algoritmo di ordinamento piú complesso, ma molto efficiente, infatti come vedremo ha una complessitá computazionale bassa.

Il meccanismo di ordinamento di questo algoritmo fa uso della tecnica Divide et Impera. Di questa tecnica ci sarebbe molto da dire, purtroppo ció esula dallo scopo di questa guida. Diciamo brevemente che é una tecnica che consiste nel suddividere ricorsivamente 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.

Vediamo nei dettagli il meccanismo di ordinamento del Merge Sort : il metodo riceve un vettore con n elementi, se nha una dimensione accettabile (che fissiamo a 20) viene ordinato con l 'Insertion Sort (scegliamo questo algoritmo poiché per piccole dimensioni di n ha buone prestazioni), altrimenti si scompone (Divide) il vettore in due parti uguali (se la dimensione é dispari la prima metà contiene un elemento in più) e su ogni meta del vettore viene richiamato ricorsivamente il metodo. Alla fine dell' invocazione dei due metodi le due sottoparti ordinate vengono fuse (Impera) con il metodo merge in un unico vettore ordinato.

Ed ecco un pratico video che ci illustra in modo semplice l'ordinamento in Java (Bubble Sort)

Dalle timide alunne Casillo Nicoletta, Pesce Luana e Ambrosio Maria.

Comment Stream