QUICK SORT

ALGORITMO:



SPIEGAZIONE ALGORTIMO

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.
E’ basato su una strategia di tipo divide et impera, ossia sull’idea di poter suddividere il problema in sottoproblemi di uguale natura, ma via via sempre più semplici da risolvere. Ovviamente tale strategia è vantaggiosa solo se lo sforzo necessario successivamente per ricomporre le soluzioni dei sottoproblemi ed ottenere la soluzione del problema iniziale, è inferiore all’impegno necessario per risolvere il problema nel suo complesso con un algoritmo diretto.
Questo tipo di strategia si presta molto bene ad essere implementata mediante un algoritmo ricorsivo, che viene applicato ad istanze sempre più piccole, fino ad arrivare ad istanze elementari del problema originale, che possano essere risolte in via diretta con una sola operazione, senza dover innescare altre chiamate ricorsive.
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 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.

L’algoritmo di quicksort inizia determinando un ipotetico valore medio, detto pivot (perno), e quindi suddivide gli elementi del vettore in due parti: quella degli elementi più piccoli e quella degli elementi più grandi del pivot.
Non è indispensabile che la suddivisione sia esattamente in parti uguali. Tuttavia, quanto più la suddivisione è esatta, tanto più l’ordinamento risulta veloce.
La stima del pivot avviene facendo semplicemente la media tra il primo e l’ultimo elemento della parte del vettore su cui si sta lavorando.



Una volta stimato il pivot, la procedura sposta tutti gli elementi di valore minore di questo nella parte sinistra del vettore, tutti quelli con valore maggiore nella parte destra.
A ogni passo la procedura quicksort ordina quindi attorno al pivot gli elementi del blocco del vettore esaminato. Man mano che i blocchi diventano sempre più piccoli, il vettore tende a essere completamente ordinato.
La procedura quicksort viene inizialmente applicata sull’intero vettore e calcola il valore della media tra gli estremi, successivamente scorre gli elementi del blocco a partire da sinistra, finche si mantengono inferiori alla media:



Analogamente la procedura scorre gli elementi del blocco a partire da destra, finchè si mantengono superiori alla media:



A questo punto se l’indice dell’elemento della parte destra del blocco è minore o uguale all’indice dell’elemento della parte sinistra, la procedura effettua lo scambio tra i rispettivi valori:



Successivamente la procedura incrementa gli indici degli elementi considerati e prosegue le scansioni da sinistra e da destra finchè i non risulti maggiore di j, condizione controllata dal ciclo repeat-until.
Quindi la procedura richiama se stessa passando nuovi valori superiori e inferiori e analizzando i blocchi sempre più piccoli del vettore:



Quando i sottoinsiemi trattati sono costituiti da un solo elemento, la ricorsione termina e la procedura restituisce al programma il vettore ordinato.


COMPLESSITA’

Nel caso migliore, effettua O(n log n) confronti per ordinare n oggetti. Tuttavia, nel caso pessimo, effettua O(n^2) confronti.
Il tempo di esecuzione dell'algoritmo Quicksort dipende dal bilanciamento del partizionamento e quindi, in particolare, da quali elementi sono stati utilizzati come perno.
Il caso peggiore si verifica quando lo sbilanciamento è totale, cioè quando l'algoritmo di partizionamento restituisce una partizione di lunghezza n-1 e una di lunghezza 1; in questo caso il tempo di esecuzione è O(n^2).
Il caso migliore si verifica quando l'algoritmo di partizionamento determina due sottoproblemi perfettamente bilanciati, entrambi di dimensione \frac{n}{2}, ottenendo quindi la stessa suddivisione del Mergesort; in questo caso il tempo di esecuzione è O(n log n).
Il caso medio è comunque molto più vicino al caso migliore che a quello pessimo.
Solitamente il quicksort è significativamente più veloce in pratica di qualsiasi altro algoritmo di complessità O(n log n) poiché la ricorsione interna può essere efficientemente implementata nella maggior parte delle architetture, e nella maggioranza dei dati utilizzati nel “mondo reale” è possibile designare le scelte migliori che minimizzano la possibilità della richiesta di un tempo quadratico.

---

Torna a Programmazione e Lab.