Hızlı sıralama

Hızlı sıralama (İngilizcesi: Quicksort), günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda,  karmaşıklığıyla, en kötü durumda ise   karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına denktir.

 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.

 Algoritma 
Hızlı sıralama algoritması, sıralanacak bir sayı dizisini daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışır.

Algoritmanın adımları aşağıdaki gibidir:
 Sayı dizisinden herhangi bir sayıyı pivot eleman olarak seç.
 Sayı dizisini pivottan küçük olan tüm sayılar pivotun önüne, pivottan büyük olan tüm sayılar pivotun arkasına gelecek biçimde düzenle (pivota eşit olan sayılar her iki yana da geçebilir). Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir. Algoritmanın bu aşamasına bölümlendirme aşaması denir.
 Pivotun sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden özyineli olarak çağrılarak sıralanır.

Algoritma içinde sayı kalmayan (eleman sayısı sıfır olan) bir alt diziye ulaştığında bu dizinin sıralı olduğunu varsayar.

 Ö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 direkt 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 direkt 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, greater
      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))

 Diğer Sıralama Algoritmaları 
 Kabarcık Sıralaması
 Birleştirmeli Sıralama
 Seçmeli Sıralama
 Kokteyl Sıralaması
 Tarak Sıralaması

 Kaynakça 

 Kaynakça 
 Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4(7), 321-322, 1961
 Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." Discrete Applied Mathematics 154(1): 1-5. 2006. 
 R. Sedgewick. Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978.
 David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press ve McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp. 145–164.
 A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379.
 Faron Moller. Analysis of Quicksort . CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
 Steven Skiena. Lecture 5 - quicksort. CSE 373/548 - Analysis of Algorithms. Department of Computer Science. State University of New York at Stony Brook.
 Conrado Martínez and Salvador Roura, Optimal sampling strategies in quicksort and quickselect. SIAM J. Computing 31(3):683-705, 2001.
 Jon L. Bentley and M. Douglas McIlroy, "Engineering a Sort Function, SOFTWARE---PRACTICE AND EXPERIENCE, VOL. 23(11), 1249–1265, 1993

 Dış bağlantılar 

 Hızlı Sıralama videosu 
 32 programlama dilinde yazılmış Hızlı Sıralama örnekleri 
 Java ile uygulanmış çok boyutlu hızlı sıralama
 Örneklerle Hızlı Sıralama eğitimi
 C dilinde uygulanmış hızlı sıralama

Kategori:Programlama
Kategori:Sıralama algoritmaları
Kategori:1961'de bilgisayar bilimi