Algoritmi di ordinamento in java

Il problema dell' ordinamento di un vettore, é 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.

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

BUBBLE SORT

Il bubble sort è un semplice algoritmo di ordinamento che funziona scorrendo ripetutamente la lista da ordinare, confrontando ogni coppia di elementi adiacenti e scambiandoli nel caso loro siano nell'ordine sbagliato. Questo passaggio viene ripetuto fin quando la lista risulterà ordinata. Quest'algoritmo prende il nome di "bubble sort" perchè imita in un certo modo il movimento delle bollicine quando salgono a galla in un bicchiere di soda.

SELECTION SORT

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 ACT

L'algoritmo solitamente ordina la sequenza sul posto. Si assume che la sequenza da ordinare sia partizionata in una sottosequenza già ordinata, all'inizio composta da un solo elemento, e una ancora da ordinare. Alla -esima iterazione, la sequenza già ordinata contiene elementi. In ogni iterazione, viene rimosso un elemento dalla sottosequenza non ordinata  e inserito nella posizione corretta della sottosequenza ordinata, estendendola così di un elemento.Simulazione dell'insertion sort su di un arrayPer fare questo, un'implementazione tipica dell'algoritmo utilizza due indici: uno punta all'elemento da ordinare e l'altro all'elemento immediatamente precedente. Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito. Il primo indice punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

MERGE SORT

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 fa uso della tecnica Divide et Impera. Diciamo brevemente che é una tecnica che 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.

Vediamo nei dettagli il meccanismo di ordinamento del Merge Sort : il metodo riceve un vettore con n elementi, se n ha una dimensione accettabile  viene ordinato con l 'Insertion Sort , altrimenti si scompone (Divide) il vettore in due parti uguali  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.

Comment Stream