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.