DAA - Hızlı Sıralama

Böl ve yönet ilkesine göre kullanılır. Hızlı sıralama, uygulaması zor olmadığı için birçok durumda tercih edilen bir algoritmadır. İyi bir genel amaçlı türdür ve yürütme sırasında nispeten daha az kaynak tüketir.

Avantajlar

Yalnızca küçük bir yardımcı yığın kullandığı için yerinde.
Sadece gerektirir n (log n) sıralama zamanı n öğeler.
Son derece kısa bir iç döngüye sahiptir.
Bu algoritma kapsamlı bir matematiksel analize tabi tutulmuştur, performans sorunları hakkında çok kesin bir açıklama yapılabilir.

Dezavantajları

Özyinelemelidir. Özellikle özyineleme mevcut değilse, uygulama son derece karmaşıktır.
En kötü durumda ikinci dereceden (yani n2) zaman gerektirir.
Kırılgandır, yani uygulamadaki basit bir hata fark edilmeyebilir ve kötü performans göstermesine neden olabilir.

Hızlı sıralama, belirli bir diziyi bölümlere ayırarak çalışır A[p ... r] iki boş olmayan alt diziye A[p ... q] ve A[q+1 ... r] öyle ki her anahtar A[p ... q] her anahtardan küçüktür veya ona eşittir A[q+1 ... r].

Ardından, iki alt dizi, Hızlı sıralama için özyinelemeli çağrılara göre sıralanır. Bölümün tam konumu verilen diziye ve dizine bağlıdırq bölümleme prosedürünün bir parçası olarak hesaplanır.

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)

Tüm diziyi sıralamak için ilk çağrının Quick-Sort (A, 1, length[A])

İlk adım olarak, Hızlı Sıralama, pivot olarak sıralanacak dizideki öğelerden birini seçer. Ardından dizi, pivotun her iki tarafında bölümlenir. Pivot'tan küçük veya ona eşit olan öğeler sola doğru hareket ederken, pivot'tan büyük veya ona eşit olan öğeler sağa doğru hareket edecektir.

Diziyi Bölümleme

Bölümleme prosedürü, alt dizileri yerinde yeniden düzenler.

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

Analiz

Hızlı Sıralama algoritmasının en kötü durum karmaşıklığı O(n²). Bununla birlikte, bu tekniği kullanarak, ortalama durumlarda genellikle çıktıyıO(n log n) zaman.