Java - Algoritmi di Ordinamento

Fonte: Wikipedia

• Il probema dell'ordinamento può essere descritto come segue. Data in input una sequenza di n numeri <a1, a2, a3, an> (in ordine qualsiasi), si vuole ottenere in output una permutazione (detta ordinamento) della sequenza di input tale che a1 <= a2 <= a3 <= an. Per questo problema sono stati proposti molti algoritmi diversi, che si differenziano da un lato per il loro costo computazionale, e dall'altro lato per la loro semplicità di implementazione.

• SELECTION SORT:
• L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in place ed in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sottosequenza ordinata, che occupa le prime posizioni dell'array, e la sottosequenza da ordinare, che costituisce la parte restante dell'array. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.

  I passi sono i seguenti:

  • si inizializza un puntatore i che va da 1 a n (dove n è la lunghezza dell'array).
  • Si cerca il più piccolo elemento dell'array
  • Scambia l'elemento più piccolo con l'elemento alla posizione i
  • Incrementa l'indice i e si torna al passo uno fino alla fine dell'array.

  Il ciclo interno è un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a N − 1 (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo è determinato dal numero di confronti. A livello asintotico viene studiato il tempo di esecuzione dei due cicli for.

  L'ordinamento per selezione effettua N(N − 1) / 2 confronti e, nel caso peggiore/migliore/medio, θ(n − 1) scambi.

  La complessità di tale algoritmo è dell'ordine di θ(n2)

• BUBBLE SORT
• Il bubble sort o bubblesort (letteralmente: ordinamento a bolle) è un semplice algoritmo di ordinamento per ordinare array. Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine in un bicchiere di champagne. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente. Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una relazione d'ordine. Non è un algoritmo efficiente: ha una complessità computazionale dell'ordine di O(n2) confronti, con n numero degli elementi da ordinare; si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità. Dell'algoritmo esistono numerose varianti, per esempio lo shakersort. Il tempo di esecuzione dell'algoritmo è Θ(n2).

• MERGE SORT
• Il merge sort è un algoritmo di ordinamento molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.
• L'idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.
• Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.
• L'algoritmo fu inventato da John von Neumann nel 1945.
• Il tempo di esecuzione dell'algoritmo Merge Sort è Θ(n log n)

• QUICK SORT
• Quicksort è un ottimo algoritmo di ordinamento ricorsivo in place che, come merge sort, si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.
• Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1960. Il Quicksort è molto popolare dato che è facilmente implementabile ed è un buon algoritmo general purpose, che ha un buon comportamento in un'ampia varietà di situazioni ed in molti casi richiede meno risorse di qualsiasi altro algoritmo. Offre inoltre il vantaggio di operare direttamente sul file da ordinare (utilizzando un piccolo stack ausiliario), e per effettuare l'ordinamento di N elementi richiede mediamente solo n \log n\! operazioni e ha un ciclo interno estremamente breve. Gli svantaggi sono dati dal fatto che non è stabile, nel caso peggiore ha un comportamento quadratico ed è particolarmente fragile: un semplice errore nella sua implementazione può passare inosservato ma causare in certe situazioni un drastico peggioramento nelle prestazioni dell'algoritmo.
• Il Quicksort è stato sottoposto a un'analisi matematica approfondita ed estremamente precisa, tanto che le sue prestazioni sono state comprese a fondo e il suo comportamento è stato descritto in modo molto accurato. I risultati ottenuti in fase di analisi sono stati verificati sperimentalmente in modo esteso e l'algoritmo di base è stato migliorato al punto da diventare il metodo ideale per un gran numero di applicazioni pratiche.
• Sono stati svolti inoltre numerosi studi per migliorare le prestazioni anche in considerazione del fatto che la ricerca di un algoritmo di ordinamento più veloce è una delle principali attrattive dell'informatica. Praticamente dal momento in cui Hoare pubblicò per la prima volta il suo lavoro, la letteratura specializzata iniziò a proporre versioni migliorate dell'algoritmo. Sono state provate e analizzate molte idee, ma l'algoritmo è così ben bilanciato da far si che il miglioramento apportato in una parte del programma quasi inevitabilmente dia luogo a un peggioramento delle prestazioni in qualche altro punto.
• Per la sua estrema facilità è stato scelto in molte librerie di linguaggi come il C di implementare di base una funzione che effettui l'ordinamento del Quicksort. C'è da tenere presente che spesso ci si può sorprendere del comportamento indesiderato e inatteso in presenza di input particolari, specialmente se si tratta di versioni dell'algoritmo messe a punto accuratamente. Se un'applicazione non giustifica il lavoro necessario ad assicurare che l'implementazione del Quicksort sia esente da errori lo Shell sort rappresenta una scelta sicura in grado di garantire prestazioni sufficientemente buone a fronte di un minore sforzo implementativo.