DAA - Ordinamento rapido
Viene utilizzato in base al principio del divide et impera. L'ordinamento rapido è un algoritmo di scelta in molte situazioni poiché non è difficile da implementare. È un buon ordinamento generico e consuma relativamente meno risorse durante l'esecuzione.
Vantaggi
È sul posto poiché utilizza solo un piccolo stack ausiliario.
Richiede solo n (log n) tempo per ordinare n elementi.
Ha un anello interno estremamente corto.
Questo algoritmo è stato sottoposto ad un'analisi matematica approfondita, è possibile fare una dichiarazione molto precisa sui problemi di prestazioni.
Svantaggi
È ricorsivo. Soprattutto, se la ricorsione non è disponibile, l'implementazione è estremamente complicata.
Richiede tempo quadratico (cioè n2) nel caso peggiore.
È fragile, cioè un semplice errore nell'implementazione può passare inosservato e causare un cattivo funzionamento.
L'ordinamento rapido funziona partizionando un dato array A[p ... r] in due sotto-array non vuoti A[p ... q] e A[q+1 ... r] tale che ogni chiave in A[p ... q] è minore o uguale a ogni chiave in A[q+1 ... r].
Quindi, i due sotto-array vengono ordinati in base a chiamate ricorsive all'ordinamento rapido. La posizione esatta della partizione dipende dall'array e dall'indice fornitiq viene calcolato come parte della procedura di partizionamento.
Algorithm: Quick-Sort (A, p, r)
if p < r then
q Partition (A, p, r)
Quick-Sort (A, p, q)
Quick-Sort (A, q + r, r)
Notare che per ordinare l'intero array, la chiamata iniziale dovrebbe essere Quick-Sort (A, 1, length[A])
Come primo passaggio, l'ordinamento rapido sceglie uno degli elementi nell'array da ordinare come pivot. Quindi, l'array viene partizionato su entrambi i lati del pivot. Gli elementi che sono minori o uguali al pivot si sposteranno verso sinistra, mentre gli elementi maggiori o uguali al pivot si muoveranno verso destra.
Partizionamento dell'array
La procedura di partizionamento riorganizza i sotto-array sul posto.
Function: Partition (A, p, r)
x ← A[p]
i ← p-1
j ← r+1
while TRUE do
Repeat j ← j - 1
until A[j] ≤ x
Repeat i← i+1
until A[i] ≥ x
if i < j then
exchange A[i] ↔ A[j]
else
return j
Analisi
La complessità del caso peggiore dell'algoritmo di ordinamento rapido è O(n2). Tuttavia, utilizzando questa tecnica, in casi medi generalmente otteniamo l'outputO(n log n) tempo.