Quicksort: differenze tra le versioni

Versione delle 20:43, 20 feb 2008

Versione delle 20:44, 20 feb 2008

Riga 9:

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 [[Charles Antony Richard Hoare|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.

== Algoritmo di Base ==

Riga 17:

Successivamente si organizzano nuovi stadi simili nei quali si procede all'ordinamento parziale delle sottosequenze di elementi rimasti non ordinati, fino al loro esaurimento.

Lo pseudocodice per il '''Quicksort''' è:

{{Matematica voce|Quicksort|Pseudocodice|

Riga 93:

In questo modo abbiamo ottenuto che l'algoritmo nel caso peggiore ha un costo quadratico. 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 0; in questo caso il tempo di esecuzione è Θ(<math>n^2</math>).

- ''';Raffinamento dell'algoritmo per ottenere come caso peggiore O(nlogn)'''.

Vogliamo evitare che la scelta del partizionamento ci conduca ad un tempo quadratico. Per fare questo è sufficiente scegliere l'elemento mediano della sequenza. La selezione del mediano può essere fatta tramite l'algoritmo [http://en.wikipedia.org/wiki/Quickselect QuickSelect], il che ci consente di trovarci sempre ad avere una sequenza di al più parte_intera_superiore(n/2) elementi, ovvero ad avere un tempo asintotico pari a O(nlogn) nel caso peggiore. Ad una analisi più accurata, tuttavia, si verifica che la costante moltiplicativa è circa 24 (e non 1.39, come nel caso migliore). Per accorgersene è sufficiente scegliere il pivot seguendo questi passi:

Riga 241:

== Partizionamento con il metodo della mediana ==

Il metodo della '''mediana di 3''' è un tipico approccio che consente di migliorare i partizionamenti dell'array, evitando partizioni troppo sbilanciate, e consiste nell'effettuare il partizionamento scegliendo opportunamente il ''pivot'' nel sottoarray: in particolare si sceglie come ''pivot'' la [[mediana (statistica)|mediana]] di un insieme di tre elementi selezionati a caso dal sottoarray.

== Chiavi duplicate ==