Algoritmi di ordinamento in Java
Il problema dell'ordinamento di un insieme, é un problema ricorrente in campo informatico che oltre ad avere un importanza fondamentale in ambito applicativo, rappresenta anche un ottimo strumento didattico per chi desidera prendere dimestichezza con la programmazione.
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 esitono 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 algorimti di semplice realizzazione, a scapito della loro complessita 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, Quick Sort).
Tutti gli algoritmi proposti si baseranno su vettori (o array) di numeri interi.
Bubble sort in Java
Tra i piú semplici algoritmi di ordinamento di Java abbiamo il Bubble Sort, che in italiano significa naturalmente ordinamento a bolle.
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 dettaglio l'algoritmo: dato un vettore con n elementi, per...
Selection sort in Java
Il Selection Sort è un altro algoritmo di ordinamento decisamente semplice ed intuitivo. L' dea 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 valore...
Insertion sort in Java
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...
Merge sort in Java
Il Merge Sort (ordinamento per fusione), a differenza degli altri algoritmi di ordinamento, é piú complesso, ma molto efficiente, infatti, come vedremo, ha un livello di complessitá computazionale piuttosto basso.
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....