Hızlı sıralama

Tarihi

Hızlı sıralama algoritması 1960 yılında küçük bir İngiliz şirketi olan Elliot Brothers'ta çalışan C. A. R. Hoare tarafından geliştirilmiştir.

Örnek

Algoritma
TEKRARLA
    Ara index_sol için
       sortFeld[index_sol] ≥ sortFeld[Pivot]
    Ara index_sağ için
       sortFeld[index_sağ] ≤ sortFeld[Pivot] 
    EĞER  index_sol ve index_sağ  bulundu ise
       SONRA Değiştir
           sortFeld[index_sol] ile sortFeld[index_sağ]
       YOKSA
           Bir element kaydır
    SON EĞER
Koşul tamamlanıncaya kadar
Üstteki algoritmaya göre asagidaki örnek :
SORTIERBEISPIEL
1 - Pivot(karşılaştırma) elementini bulmak için : 
İlk önce harfler sayılır. Eger toplam tek ise (1) ekleyip ikiye bölünür.  (15 + 1) / 2 = 8
                                    toplam çift ise ikiye bölünür.
2 - Bu durumda Pivot element B oluyor. SORTIER B EISPIEL
Burada ilk harf olan 'S' son harf olan 'L' ve orta harf olan 'B' karşılaştırılır. 
İçlerinde ortanca olan değer her zaman orta değerdir.
Yani örnek şu şekle dönüşür : SORTIER L EISPIEB
3 - Yukarıdaki algoritma göz önünde bulundurulursa; 
   Kontrol ediliyor : Soldaki element(S) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(B) Pivot(L) den küçük mü? ( Evet )
Eğer iki koşul da doğru ise ilk element(S) ile son element(B) yer değiştirilir. ( BORTIER L EISPIES ) 
(Algoritmaya göre sadece ikisi 'evet' ise değişim gerçekleşir)
                      Soldaki element(O) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )
Eğer iki koşul da doğru ise ilk element(O) ile son element(E) yer değiştirilir. ( BERTIER L EISPIOS )
                      Soldaki element(R) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(I) Pivot(L) den küçük mü? ( Evet )
Eğer iki koşul da doğru ise ilk element(R) ile son element(I) yer değiştirilir. ( BEITIER L EISPROS )
                      Soldaki element(T) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(P) Pivot(L) den küçük mü? ( Hayır )
Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor , sağdaki element(P) yi direk sağa yazılır. ( BEIIER L EISPROS )
(DİKKAT : 'T' algoritmaya şu an dahil değil, ta ki ikisi de 'evet' oluncaya kadar)
                      Soldaki element(T) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(S) Pivot(L) den küçük mü? ( Hayır )
Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor , sağdaki element(S) yi direk sağa yazılır. ( BEIIER L EISPROS )
                      Soldaki element(T) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(I) Pivot(L) den küçük mü? ( Evet )
Eğer iki koşul da doğru ise element(T) ile element(I) yer değiştirilir. ( BEIIIER L ETSPROS )
(Şimdi 'T' yazılabilir, ikisi de evet)
                      Soldaki element(E) Pivot(L) den büyük mü? ( Hayır )
                      Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )
Eğer bir koşul yanlış ise soldaki element(E) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIER L ETSPROS )
                      Soldaki element(R) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )
Eğer bir koşul da doğru ise soldaki element(R) ile sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS )
Son aşama 
                      Soldaki element(R) Pivot(L) den büyük mü? ( Evet )
                      Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )
Eğer bir koşul yanlış ise soldaki element(R) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS )
B - E - I - I - I - E - E - L - R - T - S - P - R - O - S
Aynı işlemleri sağdaki ve soldaki bölümlere ayrı ayrı yapılır.
Sonuç şöyle : 
B E E E I I I L O P R R S S T

Sözde Kodu

Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir:
 function quicksort(array)
     var list less, equal, greate
     if length(array) ≤ 1  
         return array  
     select a pivot value pivot from array
     for each x in array
         if x < pivot then append x to less
         if x = pivot then append x to equal
         if x > pivot then append x to greater
     return concatenate(quicksort(less), equal, quicksort(greater))