Quicksort: differenze tra le versioni

Versione delle 00:11, 13 apr 2008

Versione attuale delle 08:01, 29 mag 2025

(225 versioni intermedie di oltre 100 utenti non mostrate)

Riga 1:

{{Controlcopy|Parti della voce (almeno l'inizio) sembrano copiate pari pari dal testo di Sedgewick|informatica|gennaio 2011}}

[[Immagine:Quicksort_ordinamento.gif|thumb|250px|right|Quicksort]]

{{Algoritmo

[[Immagine:Quicksort example small.png|thumb|250px|right|Un'altra appresentazione grafica dell'algoritmo Quicksort]]

| classe = [[Algoritmo di ordinamento]]

'''Quicksort''' è un ottimo [[algoritmo di ordinamento]] [[Algoritmo ricorsivo|ricorsivo]] [[Algoritmo in loco|in place]] che, come [[merge sort]], si basa sul paradigma [[Divide et impera (informatica)|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.

| immagine = Sorting quicksort anim.gif

| didascalia = Quicksort in esecuzione su una lista di numeri. La linea blu è il valore del [[Pivot (matematica)|pivot]].

| struttura dati = Variabile

| tempo = <math>O(n^2)</math>

| tempo medio = <math>\Theta(n\log_2 n)</math> confronti

| tempo migliore = <math>\Omega(n\log_2 n)</math>

| spazio = Dipende dalle implementazioni

| ottimale = Spesso

}}

'''Quicksort''' è un [[algoritmo di ordinamento]] [[Algoritmo ricorsivo|ricorsivo]] [[Algoritmo in loco|in place]] non [[Algoritmo di ordinamento#Stabilit.C3.A0 di un algoritmo|stabile]]. E come l'algoritmo di ordinamento [[Merge sort|Mergesort]] basa il suo funzionamento sul paradigma del "''Divide et Impera''<ref>{{Cita web|lingua=it|url=https://www.freecodecamp.org/italian/news/gli-algoritmi-divide-et-impera/|titolo=Gli algoritmi Divide et Impera|sito=freeCodeCamp.org|data=21 luglio 2022|accesso=29 gennaio 2025}}</ref>"; ovvero sulla scomposizione del problema in più sottoproblemi di taglia minore<ref name="geeksforgeeks.org">{{Cita web|lingua=en|url=https://www.geeksforgeeks.org/quick-sort-algorithm/|titolo=Quick Sort|sito=GeeksforGeeks|data=7 gennaio 2014|accesso=29 gennaio 2025}}</ref>.

In generale la logica dell'algoritmo può essere riassunta in questo modo<ref name="geeksforgeeks.org"/>:

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 <math> N \log N\!</math> 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]].

# '''Scelta del pivot:'''

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.

#* Seleziona un elemento dell'array chiamato '''pivot'''. Può essere scelto in vari modi (es: il primo elemento, l'ultimo, un elemento casuale, o la mediana).

# '''Partizionamento della lista:'''

#* Si divide l'array in due parti:

#** Elementi minori o uguali al pivot (solitamente a sinistra del pivot)

#** Elementi maggiori del pivot (solitamente a destra del pivot)

#* Alla fine di questa fase, il pivot sarà nella sua posizione corretta nella lista.

# '''Ricorsione sui sotto-array:'''

#* Applicazione del Quicksort alla parte sinistra (elementi minori o uguali al pivot) e alla parte destra (elementi maggiori).

#* Continua fino a che i sotto-array contengono un solo elemento o sono vuoti (caso base).

Il Quicksort, termine che tradotto letteralmente in italiano significa "ordinamento rapido", è l'[[algoritmo di ordinamento]] che ha, nel caso medio, prestazioni migliori tra quelli basati su confronto. È stato ideato da [[Tony Hoare|Charles Antony Richard Hoare]] nel [[1961]].

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.

== Storia ==

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.

L'algoritmo quicksort fu ideato nel 1959 da [[Tony Hoare]] durante un viaggio nell'URSS, durante una sua visita alla [[Moscow State University]]. In quel periodo, Hoare lavorava a un progetto di [[traduzione automatica]] per il [[National Physical Laboratory, UK|National Physical Laboratory]]. Durante il processo di traduzione si rese necessario ordinare le parole russe prima di consultare il dizionario Russo-Inglese che era registrato su un [[nastro magnetico]] e ordinato alfabeticamente.<ref>{{Cita pubblicazione|cognome=Shustek|nome=L.|titolo=Interview: An interview with C.A.R. Hoare|doi=10.1145/1467247.1467261|rivista=[[Communications of the ACM|Comm. ACM]]|volume=52|numero=3|pp=38-41|anno=2009}}</ref> Dopo aver capito che l'uso dell'[[insertion sort]] sarebbe stato troppo lento, concepì una nuova idea di algoritmo - il Quicksort. Scrisse il programma con [[Autocode]] relativa alla partizione ma non riuscì a gestire la parte relativa ai segmenti non ordinati. Tornato in Inghilterra, gli fu chiesto per lavoro di scrivere il codice di uno [[Shell sort]] - l'algoritmo di ordinamento più efficiente all'epoca. Hoare dichiarò al suo capo che conosceva un algoritmo più efficiente; il capo fece una scommessa, di sei pence, e perse. In seguito, Hoare venne a conoscenza del linguaggio [[ALGOL]] e della sua abilità di gestire la ricorsione; grazie ad esso, pubblicò il codice completo nella maggiore rivista scientifica di informatica del periodo, ''[[Communications of the ACM|Communications of the Association for Computing Machinery]]''.<ref>{{Cita web|url=http://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html|titolo=My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort|data=15 marzo 2015|accesso=|editore=Marcelo M De Barros|cognome=|nome=}}</ref>

== Algoritmo di Basebase ==

L'idea base può esprimersi agevolmente in termini ricorsivi. Ad ogni stadio si effettua un ordinamento parziale di una sequenza di oggetti da ordinare. Assunto un elemento come [[Pivot (matematica)|perno]] dello stadio, si confrontano con esso gli altri elementi e si posizionano alla sua sinistra i minori e a destra i maggiori, senza tener conto del loro ordine. Dopo questo stadio si ha che il ''perno'' è nella sua posizione definitiva.

L'idea base può esprimersi agevolmente in termini ricorsivi. Ad ogni stadio si effettua un ordinamento parziale di una sequenza di oggetti da ordinare. Assunto un elemento come perno dello stadio, si confrontano con esso gli altri elementi e si posizionano alla sua sinistra i minori e a destra i maggiori, senza tener conto del loro ordine. Dopo questo stadio si ha che il ''perno'' è nella sua posizione definitiva.

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 è:

<syntaxhighlight lang="pseudo">

{{Matematica voce|Quicksort|Pseudocodice|

Procedure Quicksort(Aarray, primo, ultimo)

k ← Pivot(array, primo, ultimo)

Quicksort(array, primo, k-1)

Quicksort(array, k+1, ultimo)

Pivot(array, primo, ultimo)

Input A, vettore a₁, a₂, a₃ .. a_n

x ← array[primo]

k ← primo

for i ← primo to ultimo do

if array[i] < x then

k ← k + 1

Scambia array[i] ↔ array[k]

array[primo] ← array[k]

array[k] ← x

return k

</syntaxhighlight>

O, in alternativa:

Procedure Quicksort(A)

Input A, vettore a₁, a₂, a₃ .. a_n

begin

if n <math><=</math>≤ 1 then return A

else

begin

scegli aun casoelemento un interopivot a_{k tra 1 ed n}

calcola il vettore A1 dagli elementi a_i di A tali che i <math><></math>≠ Kk e a_i <math><=</math>≤ a_k

calcola il vettore A2 dagli elementi a_j di A tali che j <math><></math>≠ Kk e a_j <math>></math>&gt; a_k

A1 <math>:=</math>← Quicksort(A1)

A2 <math>:=</math>← Quicksort(A2)

return A1 *· (a_k) *· A2;

end

}}

C'è da notare che la partition è la funzione più discussa dagli studiosi. In molte versioni inizia la scelta del perno in modo casuale. Quindi effettua una scansione degli elementi dalla sinistra saltando quelli più piccoli e dalla destra saltando quelli più grandi, scambiando gli elementi che arrestano le scansioni e continuando fino a che i puntatori utilizzati per la scansione si incrociano. La scansione partita da sinistra si ferma una volta incontrato l'elemento perno, mentre quella partita da destra si interrompe quando arriva al carattere precedente al perno. Questo ciclo continua e l'ultima operazione da effettuare consiste nell'invertire le posizioni degli ultimi elementi che hanno interrotto la scansione.

== Specifica dell'algoritmo ==

[[ImmagineFile:SortingQuicksort quicksortexample animsmall.gifpng|thumb|300px|AnimazioneUn'altra rappresentazione grafica dell'algoritmo Quicksort]]

Si vuole fornire una versione più dettagliata dell'algoritmo che specifichi la struttura dati utilizzata e il processo di partizione. L'obiettivo è quello di implementare la procedura mediante un procedimento che calcoli la sequenza ordinata attraverso scambi diretti tra i valori delle sue componenti, senza usare vettori aggiuntivi per mantenere risultati parziali della computazione. In questo modo lo spazio di memoria utilizzato è essenzialmente ridotto alle celle necessarie per mantenere il vettore di ingresso e per implementare la ricorsione.

Si rappresenta la sequenza di input mediante il vettore <math> A = (A[1],A[2],...A[n]) \,\, n \geq 1</math> componenti. Per ogni coppia di interniinteri p,q tali che <math> 1 \leq p \leq q \leq n </math> denotiamo <math>A_{p,q} = (A[p],A[p+1],...A[q]) </math> . Il cuore dell'algoritmo è costitutocostituito dalla funzione che partiziona l'insieme, per comodità chiamiamo Partition(p,q). Questa procedura ripartisce gli elementi del vettore <math>A_{p,q}</math> rispetto al valore <math>\alpha</math> della prima componente <math>A[p]</math>; questa funzione modifica quindi il valore delle componenti di <math>A_{p,q}</math> e restituisce un indice <math> l \in [p,p+1,...q]</math> che gode delle seguenti proprietà:

# <math>A[l]</math> assume il valore <math>\alpha </math>

# <math>A_{p,l-1}</math> contiene i valori minori o uguali ad <math>\alpha </math> originariamente contenticontenuti in <math>A_{p+1,q}</math>

# <math>A_{l+1,q}</math> contiene i valori maggiori di <math>\alpha</math> originariamente contenuti in <math> A_{p+1,q}</math>

Rianalizzando l'algoritmo del quicksort prima esposto si comprende che la funzione <code>Partition(A, p, q)</code> è il fulcro delle operazioni. Nella versione qui presentata l'elemento pivot è fissato a <math>A[p]</math>; questo non è limitativo poiché il chiamante può scegliere un pivot diverso e posizionarlo in <math>A[p]</math> prima di chiamare la funzione. <code>Partition</code> quindi effettua una scansione degli elementi dalla sinistra saltando quelli più piccoli del pivot e dalla destra saltando quelli più grandi; quindi scambia gli elementi che arrestano le scansioni e ricomincia. La scansione partita da destra si ferma su elementi minori o uguali al pivot (e quindi è bloccata dall'elemento pivot stesso), mentre quella partita da sinistra si interrompe quando arriva a un elemento maggiore del pivot. I puntatori utilizzati per la scansione quindi si possono incrociare, e quando l'incrocio è avvenuto la funzione ha completato il suo lavoro.

La funzione partition può essere calcolata dalla seguente procedura nella quale due puntatori scorrono il vettore da destra a sinistra e viceversa confrontando le componenti con l'elemento scelto casualmente. Per impedire ad uno dei due puntatori di uscire dall'insieme dei valori ammissibili aggiungiamo una sentinella al vettore A, cioè una componente <math>A[n+1]</math> che assume un valore convenzionale superiore a quello di tutti gli elementi di A.

SupponiamoOltre inoltreal che il parametrovettore <math>A</math>, rappresentila unafunzione variabilericeve globale; per questo motivo gli unicii parametri formali della procedura sono <math>p</math> e <math>q</math> che rappresentano gli indici del sottovettore sul quale si opera la partizione (assumiamo sempre <math> 1 \leq p \leq q \leq n </math>). Le altre variabili che compaiono nella procedura sono locali.

Function Partition(A, p, q)

begin

{{Matematica voce|Quicksort|Partition|

i ← p

Function Partition(p,q)

j ← q

begin

while i ≤ j do

i <math>:=</math> p <math>+</math> 1

begin

j <math>:=</math> q

while A[j] &gt; A[p] do j ← j - 1

while i <math><</math> j do

while i ≤ j and A[i] ≤ A[p] do i ← i + 1

begin

while A[j]if <math>></math> A[p] do ji <math>:=</math> j - 1then

begin

while A[i] <math>\leq</math> A[p] E i <math>\leq</math> j do i <math>:=</math> i <math>+</math> 1

if i <math><</math> j then Scambia(A[i], A[j])

begin i ← i + 1

Scambia(A[i],A[ j]) ← j - 1

i <math>:=</math> i <math>+</math> 1end

end

j <math>:=</math> j <math>-</math> 1

Scambia(A[p], A[j])

end

return endj

end

Scambia(A[p],A[j])

return j

end}}

Rianalizzando l'algoritmo del quicksort prima esposto si comprende che la funzione partition è il fulcro delle operazioni.

== Analisi delle prestazioni ==

=== Caso peggiore ===

Denotiamo con <math>T_w(n)</math> il massimo numero di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo su input A di lunghezza n. È evidente che i vettori A1 e A2 della partizione possono essere calcolati mediante n-1 confronti (dato che un elemento viene scelto come pivot). Inoltre la dimensione di A1 e A2 è data rispettivamente da k e n-k-1, per qualche <math> k \in [0,1,...,n-1]</math>. Questo implica che per ogni <math> n \geq 1 </math>:

Denotiamo con <math>T_w(n)</math> il massimo numero di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo su input <math>A</math> di lunghezza <math>n</math>. È evidente che i vettori <math>A_1</math>e <math>A_2</math> della partizione possono essere calcolati mediante <math>n-1</math> confronti (dato che un elemento viene scelto come [[Pivot (matematica)|pivot]]). Inoltre la dimensione di <math>A_1</math>e <math>A_2</math> è data rispettivamente da <math>k</math> e <math>n-k-1</math>, per qualche <math> k \in [0,1,...,n-1]</math>. Questo implica che per ogni

<math> T_w(n) = n - 1 + max_{0\leq k \leq n-1}{T_w(k) + T_w(n-k-1)}</math>

<math> n \geq 1 </math>:

<math display="block"> T_w(n) = n - 1 + max_{(0\leq k \leq n-1)}{T_w(k) + T_w(n-k-1)}</math>

mentre per n = 0

mentre per <math> n = 0 </math>:<math display="block"> T_w(0) = 0</math>

<math> T_w(0) = 0</math>. Questa è l'equazione di ricorrenza per l'algoritmo in questione.

Si vuole ora determinare il <math>T_w(0)</math> esatto. Nel caso pratico questo valore sarà utile per capire il comportamento dell'algoritmo nel caso in cui si sceglie l'elemento massimo o minimo per il partizionamento (il caso peggiore). Infatti poiche <math> max_{0\leq k \leq n-1}[T_w(k) + T_w(n-k-1)]\geq T_w(n-1) </math> abbiamo che <math> T_w(n) \geq n - 1 + T_w(n -1) </math> e quindi per ogni <math> n \in N </math> otteniamo:

Questa è l'equazione di ricorrenza per l'algoritmo in questione.

<math> T_w(n) = \sum_{0}{n-1} k = \frac {n (n -1) } {2} </math>.

Si vuole ora determinare il <math>T_w(0)</math> esatto. Nel caso pratico questo valore sarà utile per capire il comportamento dell'algoritmo nel caso in cui si sceglie l'elemento massimo o minimo per il partizionamento. Infatti poiché <math display="inline"> max_{(0\leq k \leq n-1)}[T_w(k) + T_w(n-k-1)]\geq T_w(n-1) </math> abbiamo che <math> T_w(n) \geq n - 1 + T_w(n -1) </math> e quindi per ogni <math> n \in N </math> otteniamo:

<math display="block"> T_w(n) = \sum_{0}^{n-1} k = \frac {n (n -1) } {2} </math>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>).

Se vogliamo evitare che la scelta del partizionamento ci conduca ad un tempo quadratico, è sufficiente scegliere come pivot l'elemento mediano della sequenza, per esempio tramite l'algoritmo [[Quickselect|QuickSelect]]. Questo consente di trovarci sempre ad avere due sequenze di <math>\lfloor n/2 \rfloor </math> elementi, ottenendo quindi un tempo asintotico pari a <math display="inline">O(n \log_2 n)</math> nel caso peggiore. Ad un'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:

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

# Costruire <math>n/5</math> quintuple: l'ultimo sottoarray può non essere una quintupla, ma un insieme più piccolo;

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:

# Per ogni quintupla calcolare il mediano, effettuando in totale, <math>7n/5</math> confronti, perché il mediano di 5 elementi può essere calcolato con al più 7 confronti;

- Costruire n/5 quintuple: l'ultimo sottoarray può non essere una quintupla (ma un insieme più piccolo)

# Ricavare un campione, ottenuto come mediano dei mediani delle quintuple;

- Per ogni quintupla calcolare il mediano, effettuanto in totale, 7n/5 confronti, perché il mediano di 5 elementi può essere calcolato con al più 7 confronti.

-# RicavareCalcolare unil campione, ottenutopivot come mediano dei mediani, impiegando un tempo pari a <math display="inline">T(n/5)</math> delle(chiamata quintuplericorsiva);

# Partiziona intorno al pivot: <math>(n-1)</math> confronti;

- Calcolare il pivot come mediano dei mediani, impiegando un tempo pari a T(n/5) (chiamata ricorsiva)

# Prosegui ricorsivamente: <math display="inline">T(\frac{7}{10}n)</math> (perché la chiamata viene effettuata un insieme con cardinalità pari, al più <math display="inline">\tfrac{7}{10} n + 3</math>).

5. Partiziona intorno al pivot: (n-1) confronti (ovvio)

6. Prosegui ricorsivamente: T( (7/10) n ) (perché la chiamata viene effettuata un insieme con cardinalità pari, al più 7n/10 +3).

L'equazione di ricorrenza diventa:

<math>T(n) ≤\le (12/5)\ n + T( n/5 ) + T( (7/10)\ n )</math>

che ha soluzione <math>O(n)</math>, in particolare <math>T(n)<= \le cn <->\longleftrightarrow c > 24</math>. Esistono quindi soluzioni approssimate che in pratica evitano il caso pessimo pur non potendo garantire ciò.

=== Caso medio ===

Per lo studio nel caso medio si valuta il numero medio di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo, determinando di conseguenza l'ordine di grandezza del tempo medio di calcolo necessario per eseguire la procedura.

Per lo studio nel caso medio si valuta il numero medio di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo, determinando di conseguenza l'ordine di grandezza del tempo medio di calcolo necessario per eseguire la procedura.

La complessità dell'algoritmo in questo caso è <math>O (n \log_2 (n))</math>, precisamente <math display="inline">1.39\ n \log_2(n)</math>.

=== Caso migliore ===

Il caso migliore si verifica quando l'algoritmo di partizionamento determina due sottoproblemi perfettamente bilanciati, entrambi di dimensione ''n/2''; in questo caso il tempo di esecuzione è Θ(nlogn), precisamente 1.39NlogN.

Il caso migliore si verifica quando l'algoritmo di partizionamento determina due sottoproblemi perfettamente bilanciati, entrambi di dimensione ''n/2''; in questo caso il tempo di esecuzione è <math display="inline">O(n \log_2(n))</math>.

== Tipi di partizionamento ==

Esistono delle varianti del quicksort che si basano sulla differente scelta dell'elemento pivot all'interno della serie di dati da ordinare.

* '''Non casuale (non random)''': in questa versione si sceglie come pivot l'elemento in ultima posizione evitando in questo modo il calcolo della scelta dei numeri casuali. Il caso pessimo è rappresentato da un vettore ordinato al contrario. Anche qualora venga scelto un altro elemento come pivot (ad es. il primo o quello di mezzo) si può trovare un caso pessimo.

* '''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. Anche in questo caso tuttavia esiste un caso pessimo ed ha complessità quadratica.

*'''Casuale (random)''': Questa è la prima versione pubblicata del quicksort che si basa sulla scelta casuale dell'elemento pivot. Questo non permette di stabilire a tavolino quale sia il caso peggiore, che tuttavia si verificherà con probabilità <math display="inline">O((1/n)^{\log n})</math>.

Come già menzionato in precedenza, tutte queste versioni si ottengono aggiungendo uno scambio prima della chiamata a <code>Partition</code>, per esempio:

scegli a caso un intero k tra p e q

Scambia (A[p], A[k])

Partition (A, p, q)

=== Chiavi duplicate ===

Se nello stesso vettore esistono degli elementi ripetuti, è possibile sistemarli nella prima scansione che viene effettuata tramite la versione di Bentley - Mc Illroy del 1993.

Questa versione prevede che, durante il processo di scansione (fase di partizionamento dell'algoritmo), gli elementi uguali al pivot vengano spostati immediatamente a fianco del pivot (a sinistra se provengono dalla parte sinistra, a destra se provengono dalla parte destra). In questo modo si avranno tre partizioni, una con gli elementi minori del pivot, una con gli elementi uguali e una con gli elementi maggiori del pivot.

La complessità dell'algoritmo non viene modificata.

== Dimensione dello stack ==

L'[[algoritmo]] utilizza la ricorsione, che in casi di anomalie potrebbe portare a problemi di STACK[[stack OVERFLOWoverflow]]. È possibile operare un processo di rimozione della ricorsione senza alterare le prestazioni utilizzanoutilizzando ununo stack esterno che memorizza il "lavoro da fare" in forma di file parziali da ordinare. Ogni qualvolta si richiede un sottofile da ordinare è sufficiente estrarlo dalla stack mentre in seguito a un partizionamento i due file parziali generati possono essere inseritivi. Nell'implementazione ricorsiva (quelle viste sopra), lo stack viene gestito dal sistema contiene le stesse informazioni che si salveranno in questo stack esterno. Per un flefile casuale la massima dimensione dello stack è proporzionale a <math> \log n</math> anche se in casi degeneri lo stack può crescere proporzinalmenteproporzionalmente a N. Il caso peggiore è quello in cui il file risulta già ordinato. Questo problema è tanto sottile quanto reale: anche un programma ricorsivo utilizza (implicitamente ) uno stack, per cui la degenerazione del quicksort per file di grandi dimensioni potrebbe casuarecausare una terminazione anomala del programma per mancanza di memoria disponibile. Ovviamente un comportamento del genere deve essere evitato soprattutto se si vuole inserire la routine in una libreria di programma. Non è facile dare garanzie che ciò non avvenga anche se non è difficile fare in modo che questi casi degeneri siano estramenteestremamente improbabili.

Per effettuare lo studio della dimensione dello stack si effettua la valutazione dello spazio di memoria necessario alla procedura del quicksort. Oltre alle n celle necessarie per contenere il vettore dei valori di ingresso, occorre utilizzare una certa quantità di spazio per mantenere la pila che implementa la ricorsione. Nel caso peggiore <code>Quicksort(1,n)</code> utilizza uno spazio <math>O(n)</math> per mantenere la pila. Se infatti viene estratto l'elemento maggiore del campione, la pila deve conservare i parametri relativi a un massimo di <math>n - 1 </math>chiamate ricorsive.

=== Quicksort iterativo ===

Riga 123 ⟶ 173:

Il primo passaggio da fare per passare dalla strategia ricorsiva a quella iterativa è quello di inserire il più grande dei due sottofile da ordinare nello stack assicurando che ogni sottofile presente nello stack non sia più grande della metà di quello che gli sta sotto, quindi lo stack non dovrà contenere più di un numero logaritmico di oggetti. Questa dimensione massima dello stack si verifica quando il partizionamento è effettuato sempre al centro del file. Per file casuali l'occupazione di stack è verosimilmente piccola.

La versione di base del quicksort potrà essere miglioraremigliorata modificando appositamente le chiamate ricorsive. Più precisamente si può forzare la procedura ad eseguire sempre la prima chiamata relativa al sottovettore di lunghezza minore. Si ottiene un nuovo algoritmo con le seguenti istruzioni (la procedura viene scritta in pseudocodice):

Procedure Quicksort(A, p, q)

{{Matematica voce|Quicksort|Ricorsiva Migliorata|

Input A vettore di elementi

Procedure Quicksort(a)

Input A vettore di elementi

begin

if l - q <math><</math> q - l then

begin

if p <math><</math> l - 1 then Quicksort (p,l-1)

if l + 1 <math><</math> q then Quicksort (l + 1, q)

end

else

begin

if l+1 <math><</math>← qPartition then(A, Quicksortp, (l+1,q)

if p <math><</math> (l -1 thenp) Quicksort&lt; (p,lq -1 l) then

begin

if p &lt; (l - 1) then Quicksort(A,p, l - 1)

if (l + 1) &lt; q then Quicksort(A, l + 1, q)

end

else

begin

if (l + 1) &lt; q then Quicksort(A, l + 1,q)

if p &lt; (l - 1) then Quicksort(A,p, l - 1)

end

end

end

A questo punto è possibile operare la trasformazione e passare nella versione iterativa. Si osserva innanzitutto che in questo caso il criterio di gestione della pila può essere semplificato sfruttando il fatto che le due chiamate ricorsive sono le ultime istruzioni della procedura. Si può quindi definire una versione iterativa nella quale la pila serve per mantenere l'elenco delle chiamate che devono ancora essere eseguite e non sono state neppure iniziate. In altre parole nell'esecuzione della procedura la prima chiamata ricorsiva viene attivata dopo aver accantonato in testa alla pila i parametri necessari per eseguire la seconda. Quest'ultima sarà attivata una volta completata la precedente, quando i suoi parametri si trovano di nuovo in testa alla pila. In particolare non si ha bisogno di mantenere nella pila il record di attivazione della procedura (che qualsiasi [[linguaggio di programmazione]] fa ogni qual volta viene chiamata una procedura).

}}

A questo punto è possibile operare la trasformazione e passare nella versione iterativa. Si osserva innanzitutto che in questo caso il criterio di gestione della pila può essere semplificato sfruttando il fatto che le due chiamate ricorsive sono le ultime istruzioni della procedura. Si può quindi definire una versione iterativa nella quale la pila serve per mantenre l'elenco delle chiamate che devono ancora essere eseguite e non sono state neppure iniziate. In altre parole nell'esecuzione della procedura la prima chiamata ricorsiva viene attivata dopo aver accantonato in testa alla pila i parametri necessari per eseguire la seconda. Quest'ultima sarà attivata una volta completata la precedente, quando i suoi parametri si trovano di nuovo in testa alla pila. In particolare non si ha bisogno di mantenere nella pila il record di attivazione della procedura (che qualsiasi linguaggio di programmazione fa ogni qual volta viene chiamata una procedura).

L'algoritmo così ottenuto è descritto dalla seguente procedura:

{{Matematica voce|Quicksort|Iterativa|

procedureProcedure Quicksort iterativo (A)

Input: un vettore A con i dati da ordinare

begin

p <math>:=</math>← 1

q <math>:=</math>← n

S <math>:=</math>← NULL

repeat

while (q <math>-</math> p) <math>\geq</math>≤ 1 do

begin

scegli a caso un intero k traPartition(A, p e, q )

Scambia (A[p],A[k])

esegui la Partition(p,q)

sia A_p1,q1 il vettore max(A_p,q)

sia A_p2,q2 il vettore min(A_p,q)

S<math>:=</math> ← Push(S, (p1,q1))

p<math>:=</math> ← p2

q<math>:=</math> ← q2

end

until (S <math>=</math> NULL) Oor (q - p) <math><</math>&lt; 1

end

}}

Si può dimostrare che la procedura è corretta. Infatti al termine dell'esecuzione di ogni ciclo repeat-until le parti del vettore di ingresso non ancora ordinate sono contenute nella pila S oppure in A<submath>A_{p,q}</submath>. La verifica di questa proprietà è facile. Di conseguenza quando si esce dal ciclo la condizione <code>(S ≠ NULL)</code> NULL Ee <code>(q - p) < 1</code> garantisce che il vettore di ingresso sia ordinato.

=== Valutazione altezza massima dello stack ===

Si osserva innanzitutto che il vettore A_p,q sul quale la macchina sta lavorando non è mai maggiore del vettore che si trova in testa alla pila S. Inoltre, ad ogni incremento di S la dimensione A_p,q, viene ridotta almento della metà. Quindi durante la computazione la pila può contenere al più <math> log_2 N</math> elementi dove n è la dimensione dell'input.

Si osserva innanzitutto che il vettore <math>A_{p,q}</math> sul quale la macchina sta lavorando non è mai maggiore del vettore che si trova in testa alla pila S. Inoltre, ad ogni incremento di S la dimensione <math>A_{p,q}</math>, viene ridotta almeno della metà. Quindi durante la computazione la pila può contenere al più <math> log_2(n)</math> elementi dove <math>n</math> è la dimensione dell'input.

=== Quicksort misto ricorsivo-iterativo ===

Come descritto per il Quicksort iterativo, anche per questa strategia il primo passo è quello di modificare la procedura ricorsiva considerando il fatto che la seconda chiamata alla funzione QuicksotQuicksort avviene alla fine della procedura, quando non c'è più quindi la necessità di mantenere nello stack le informazioni e lo stato della funzione chiamante. Si può allora trasformare la seconda chiamata ricorsiva in un loop interno alla funzione chiamante stessa, dopo averne opportunamente aggiornato i parametri d'ingresso. Se a questo primo passo aggiungiamo che la prima chiamata ricorsiva nonè la effettuiamo a caso,sempre maeffettuata sulla parte di vettore da ordinare che risulta più corta (e quindi mai maggiore della metà del vettore di partenza), otteniamo contemporaneamente unaquesta strategia che:contemporaneamente riduce il numero di chiamate ricorsive, utilizzae può utilizzare lo stack di sistema (senza doverne creare uno ad hoc,) dato che limita la profondità massima dello stack, anche nel caso peggiorepessimo, a <math display="inline"> log_2 N(n)</math> elementi.

Si riporta una efficiente implementazione in [[linguaggio C|C]] della strategia descritta. Il codice può essere compilato per ordinare stringhe, numeri interi, etc.

<syntaxhighlight lang="c">

{{Matematica voce|Quicksort|misto ricorsivo-iterativo|

<code><pre><nowiki>

/********** QuickSort(): sorts the vector 'list[]' **********/

Riga 207 ⟶ 255:

while (1)

{

while ( (l<=r) && ( QS_COMPARE(list[l],piv) <= 0 ) ) l++;

while ( (l<=r) && ( QS_COMPARE(list[r],piv) > 0 ) ) r--;

if (l>r) break;

Riga 235 ⟶ 283:

}

}

</syntaxhighlight>

</nowiki></pre></code>

}}

== Stringhe e vettori ==

== File parziali di piccole dimensioni ==

{{...| informatica}}

== Selezione ==

== Partizionamento con il metodo della mediana ==

{{...| informatica}}

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 duplicateNote ==

<references/>

== Stringhe e vettori ==

== Selezione ==

==Implementazioni==

{{Trasferimento|wb|Implementazioni}}

Seguono alcuni esempi di implementazione in vari [[linguaggi di programmazione|linguaggi]].

===[[linguaggio C|C]]===

{{Matematica voce|Quicksort|C|

<source lang="C">

void sort(int array[], int begin, int end) {

int pivot, l, r;

if (end > begin) {

pivot = array[begin];

l = begin + 1;

r = end+1;

while(l < r)

if (array[l] < pivot)

l++;

else {

r--;

swap(array[l], array[r]);

}

l--;

swap(array[begin], array[l]);

sort(array, begin, l);

sort(array, r, end);

}

}

</source>

}}

//attenzione, il programma non è completo!

===[[C++]]===

{{Matematica voce|Quicksort|C++|

<source lang="Cpp">

#include <algorithm>

#include <iterator>

#include <functional>

template <typename T>

void sort(T begin, T end) {

if (begin != end) {

T middle = partition (begin, end, bind2nd(

less<iterator_traits<T>::value_type>(), *begin));

sort (begin, middle);

sort (max(begin + 1, middle), end);

}

}

</source>

}}

=== [[Haskell]] ===

{{Matematica voce|Quicksort|Haskell|

<code><pre><nowiki>

sort :: (Ord a) => [a] -> [a]

sort [] = []

sort (pivot:rest) = sort [y | y <- rest, y < pivot]

++ [pivot] ++

sort [y | y <- rest, y >=pivot]

</nowiki></pre></code>

}}

=== [[Linguaggio di programmazione Java|Java]] ===

Questo esempio mostra un quicksort generico, piuttosto che uno che funzioni con gli interi o con le stringhe.

{{Matematica voce|Quicksort|Java|

<source lang="java">

import java.util.Comparator;

import java.util.Random;

public class Quicksort {

public static final Random RND = new Random();

private void swap(Object[] array, int i, int j) {

Object tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}

private int partition(Object[] array, int begin, int end, Comparator cmp) {

int index = begin + RND.nextInt(end - begin + 1);

Object pivot = array[index];

swap(array, index, end);

for (int i = index = begin; i < end; ++ i) {

if (cmp.compare(array[i], pivot) <= 0) {

swap(array, index++, i);

}

}

swap(array, index, end);

return (index);

}

private void qsort(Object[] array, int begin, int end, Comparator cmp) {

if (end > begin) {

int index = partition(array, begin, end, cmp);

qsort(array, begin, index - 1, cmp);

qsort(array, index + 1, end, cmp);

}

}

public void sort(Object[] array, Comparator cmp) {

qsort(array, 0, array.length - 1, cmp);

}

}

</source>

ATTENZIONE NON FUNZIONA!

ATTENZIONE NON FUNZIONA!

ATTENZIONE NON FUNZIONA!

ATTENZIONE NON FUNZIONA!

ATTENZIONE NON FUNZIONA!

Ecco un algoritmo che funziona solo con numeri interi :

<source lang="java">

public void QuickSort( int [] v , int in , int fin ){

if( fin<=in )return;

int pos=partiziona( v,in,fin );

/*

*Ricorsione...(Quindi algoritmo non in-place , in quanto deve

*allocare memoria fino alla risoluzione del problema)

*/

QuickSort( v,in,pos-1 );

QuickSort( v,pos+1,fin );

}

public int partiziona( int[]v , int in , int fin ){

// L'elemento pivot è il primo (posizione 0)

int i=in+1,j=fin;

while( i<=j ){

while( (i<=fin) && (v[i]<=v[fin]) ) i++;

while( v[j]>v[in] ) j--;

if( i<=j ){

// Scambia

int t=v[i];

v[i]=v[j];

v[j]=t;

}

}

// Scambia

int tt=v[in];

v[in]=v[i-1];

v[i-1]=tt;

return i-1;

}

</source>

}}

=== [[Joy_(programmazione)|Joy]] ===

{{Matematica voce|Quicksort|Joy|

<code><pre><nowiki>

DEFINE sort == [small][]

[uncons [>] split]

[[swap] dip cons concat] binrec .

</nowiki></pre></code>peido

}}

===[[Lisp]]===

{{Matematica voce|Quicksort|Lisp|

<source lang="Lisp">

(defun qsort (lst cmp / x y l e g)

(if lst

(progn

(setq x (nth (/ (length lst) 2) lst))

(foreach y lst

(cond

((equal y x)

(setq e (cons y e)))

((apply cmp (list y x))

(setq l (cons y l)))

(T (setq g (cons y g)))

)

)

(append (qsort l cmp) e (qsort g cmp))

)

)

)

</source>

}}

===[[Pascal]]===

{{Matematica voce|Quicksort|Pascal|

<source lang="pascal">

procedure pQuickSort(var A: array of integer; iLo, iHi: integer);

var Lo, Hi, Pivot, T: Integer;

begin

Lo := iLo; Hi := iHi;

Pivot := A[Hi]; {Pivot is right}

repeat

while A[Lo] < Pivot do Inc(Lo);

while A[Hi] > Pivot do Dec(Hi);

if Lo <= Hi then begin

T := A[Lo]; A[Lo] := A[Hi]; A[Hi] := T;

Inc(Lo); Dec(Hi);

end;

until Lo > Hi;

if Hi > iLo then pQuickSort(A, iLo, Hi); {Sort left Part}

if Lo < iHi then pQuickSort(A, Lo, iHi); {Sort right Part}

end;

begin

pQuickSort(A, Low(A), High(A)); {First Call of the whole}

{Implemented by Markus Gronotte in Pascal}

end;

</source>

}}

=== [[Perl|Perl]] ===

{{Matematica voce|Quicksort|Perl|

<source lang="perl">

sub qsort {

@_ or return ();

my $p = shift;

(qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));

}

</source>

}}

=== [[Perl|Perl 6]] ===

{{Matematica voce|Quicksort|Perl 6|

<source lang="perl">

multi quicksort () { () }

multi quicksort (*$x, *@xs) {

my @pre = @xs.grep:{ $_ < $x };

my @post = @xs.grep:{ $_ >= $x };

(@pre.quicksort, $x, @post.quicksort);

}

</source>

}}

=== [[Python]] ===

{{Matematica voce|Quicksort|Python|

Ordinamento in place:

<source lang="python">

def partition(array, begin, end, cmp):

pivot=array[end]

ii=begin

for jj in xrange(begin, end):

if cmp(array[jj], pivot):

array[ii], array[jj] = array[jj], array[ii]

ii+=1

array[ii], array[end] = pivot, array[ii]

return ii

def sort(array, cmp=lambda x, y: x < y, begin=0, end=None):

if end is None: end = len(array)

if begin < end:

i = partition(array, begin, end-1, cmp)

sort(array, cmp, begin, i)

sort(array, cmp, i+1, end)

</source>

Algoritmo funzionale:

<source lang="python">

def quicksort(lista):

if len(lista)<=1: return lista

pivot=lista[0]

return (quicksort([e for e in lista[1:] if e < pivot]) +

[pivot] +

quicksort([e for e in lista[1:] if e >= pivot]))

</source>

}}

=== [[Prolog]] ===

{{Matematica voce|Quicksort|Prolog|

<code><pre><nowiki>

append([], L, L).

append([H | L1], L2, [H | Result]) :- append(L1, L2, Result).

partition([], _, [], []).

partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right).

partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right).

qsort([],[]).

qsort([H | Tail], Sorted) :-

partition(Tail, H, Left, Right),

qsort(Left, SortedLeft),

qsort(Right, SortedRight),

append(SortedLeft, [H | SortedRight], Sorted).

</nowiki></pre></code>

}}

===[[Ruby]]===

{{Matematica voce|Quicksort|Ruby|

<source lang="ruby">

def qsort(list)

return [] if list.size == 0

x, *xs = *list

less, more = xs.partition{|y| y < x}

qsort(less) + [x] + qsort(more)

end

</source>

}}

=== [[Standard ML|SML]] ===

{{Matematica voce|Quicksort|SML|

<code><pre><nowiki>

'''fun''' quicksort lt lst =

'''let''' val rec sort =

fn [] => []

| (x::xs) =>

'''let'''

val (left,right) = List.partition (fn y => lt (y, x)) xs

'''in''' sort left @ x :: sort right

'''end'''

'''in''' sort lst

'''end'''

</nowiki></pre></code>

}}

== Bibliografia ==

* Hoare, C. A. R. (1961): ''Partition: Algorithm 63'', ''Quicksort: Algorithm 64'', and ''Find: Algorithm 65.'', Comm. ACM 4, pp. 321-322&nbsp;321–322

* Sedgewick, Robert (1978): ''Implementing quicksort programs'', Communications of the ACM, 21(10) pp. 847-857&nbsp;847–857.

* Musser, David (1997): ''Introspective Sorting and Selection Algorithms'', Software Practice and Experience vol 27, number 8, pp. 983-993&nbsp;983–993

* LaMarca, A.; Ladner, R. E. (1997): ''The Influence of Caches on the Performance of Sorting'', Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 370-379&nbsp;370–379.

== Voci correlate ==

* [[qsort]] - Funzione di ordinamento presente nella [[libreria standard del C]], che tipicamente implementa l'algoritmo di ordinamento quicksort.

== Altri progetti ==

{{interprogetto|b_oggetto=implementazioni|b_preposizione=del|preposizione=sul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

*[http://pages.stern.nyu.edu/~panos/java/Quicksort/ Interactive quicksort]

* {{FOLDOC}}

*[http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort Multidimensional quicksort in Java]

* {{cita web|http://pages.stern.nyu.edu/~panos/java/Quicksort/|Interactive quicksort}}

*[http://www.datastructures.info/what-is-quicksort-and-how-does-it-work-quick-sort-algorithm/ Video spiegazione di Quicksort usando le schede e del codice in C++]

* {{cita web | 1 = http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort | 2 = Multidimensional quicksort in Java | accesso = 26 dicembre 2005 | urlarchivio = https://web.archive.org/web/20051124012106/http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort | dataarchivio = 24 novembre 2005 | urlmorto = sì }}

{{Ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[ar:ترتيب سريع]]

[[bg:Бързо сортиране]]

[[bn:কুইক সর্ট]]

[[ca:Quicksort]]

[[cs:Quicksort]]

[[de:Quicksort]]

[[en:Quicksort]]

[[es:Quicksort]]

[[fa:کوییک‌سورت]]

[[fi:Pikalajittelu]]

[[fr:Tri rapide]]

[[he:מיון מהיר]]

[[hu:Gyorsrendezés]]

[[is:Snarröðun]]

[[ja:クイックソート]]

[[ko:퀵 정렬]]

[[lt:Greitojo rikiavimo algoritmas]]

[[nl:Quicksort]]

[[no:Quicksort]]

[[pl:Sortowanie szybkie]]

[[pt:Quicksort]]

[[ru:Быстрая сортировка]]

[[sk:Quicksort]]

[[sl:Hitro urejanje]]

[[sv:Quicksort]]

[[tr:Hızlı sıralama]]

[[uk:Швидке сортування]]

[[uz:Quicksort]]

[[vi:Sắp xếp nhanh]]

[[zh:快速排序]]