If you're seeing this message, it means we're having trouble loading external resources on our website.

Bağlandığınız bilgisayar bir web filtresi kullanıyorsa, *.kastatic.org ve *.kasandbox.org adreslerinin engellerini kaldırmayı unutmayın.

Ana içerik

Hızlı sıralamaya genel bakış

Birleştirme Sıralaması(Merge Sort), gibi, Hızlı Sıralama (Quick Sort) da böl ve yönet kullanır ve bu nedenle özyinelemeli bir algoritmadır. Hızlı sıralamanın böl ve yönet yöntemini kullanma şekli, birleştirme sıralaması yönteminden biraz farklıdır. Birleştirme sıralamasında, bölme adımı neredeyse hiçbir şey yapmaz ve işin neredeyse tamamı birleştirme adımında gerçekleşir. Hızlı sıralamada tam tersidir: tüm gerçek iş bölme adımında gerçekleşir. Hızlı sıralamadaki birleştirme adımı hiçbir şey yapmaz.
Hızlı Sıralaması, birleştirme sıralamasına göre birkaç farklılığa sahiptir. Hızlı sıralama yerinde çalışır. Ve en kötü durumdaki çalışma süresi, seçimli sıralama ve eklemeli sıralama kadar kötüdür: Θ(n2). Ancak ortalama durumdaki çalışma süresi, birleştirme sıralaması kadar iyidir: Θ(nlog2n).
Öyleyse, birleştirme sıralaması en az bu kadar iyiyken neden hızlı sıralamayı düşünelim? Bunun nedeni, hızlı sıralama için büyük-Θ notasyonunda gizlenen sabit faktörün oldukça iyi olmasıdır. Pratikte, hızlı sıralama, birleştirme sıralamasından daha iyi performans gösterir ve seçim sıralama ve ekleme sıralamasından önemli ölçüde daha iyi performans gösterir.
Hızlı sıralama (Quicksort) böl ve yönet yöntemini aşağıdaki gibi kullanır. Birleştirme sıralamasında olduğu gibi, asıl dizi dizi[0..n-1] ise onun bir alt dizisi olan dizi[p..r] yi sıralamayı düşünün.
  1. dizi[p..r] alt dizisindeki herhangi bir öğeyi seçerek bölün. Bu öğeyi pivot olarak adlandırın.
dizi[p..r] içindeki öğelerin yerlerini öyle değiştirin ki, dizi[p..r] içindeki pivottan küçük veya pivota eşit olan tüm öğeler pivotun solunda olsun ve pivottan daha büyük olan tüm öğeler pivotun sağında olsun. Bu işleme bölümlendirme (partitioning) deriz. Bu noktada, pivotun sağ ve sol taraflarındaki öğelerin ne şekilde sıralandığının bir önemi yoktur. Sadece öğelerin doğru tarafta olmaları önemlidir.
Pratikte, pivot olarak her zaman en sağdaki öğeyi, `dizi[r]`, seçeriz. Örneğin, alt dizi [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]'dan oluşuyorsa, pivot olarak 6'yı seçeriz. Alt dizi bölümlemeden sonra [5, 2, 3, 6, 12, 7, 14, 9, 10, 11] olabilir. Pivotun bölümlemeden sonraki indeksi `q` olsun.
  1. Yönet (conquer): Bölümlendirmeden sonraki alt dizileri, dizi[p..q-1] (pivotun solundaki, pivottan küçük veya pivota eşit, tüm öğeler) ve dizi[q+1..r] (pivotun sağındaki, pivottan büyük, tüm öğeler), özyinelemeli olarak sıralayalım.
  2. Birleştirme adımına görev kalmaz. Yönet adımı özyinelemeli olarak sıralamayı bitirdiğinde, işlem tamamlanmış olur. Peki, neden? Pivotun solunda olan, dizi[p..q-1] alt dizisinin tüm öğeleri pivottan küçük veya ona eşittir ve sıralanmışlardır. Ayrıca, pivotun sağında olan, dizi[q+1..r] alt dizisinin tüm öğeleri pivottan daha büyüktür ve sıralıdırlar. Sonuç olarak, dizi[p..r] sıralanmış hâle gelir.
    Örneğimizi düşünelim. Pivotun solundaki ve sağındaki alt dizileri yinelemeli olarak sıraladıktan sonra, pivotun solundaki alt dizi [2, 3, 5] ve pivotun sağındaki alt dizi [7, 9, 10, 11, 12, 14] olur. Yani alt dizide [2, 3, 5], ardından 6 ve ardından [7, 9, 10, 11, 12, 14] gelir. Alt dizi sıralanmış olur.
Temel durumlar, birleştirme sıralamasında olduğu gibi, ikiden daha az öğeden oluşan alt dizilerdir. Birleştirmeli sıralamada, hiçbir zaman elemanı olmayan bir alt dizi görmeyiz, ancak alt dizideki diğer öğelerin tümü pivottan küçükse veya tümü pivottan büyükse hızlı sıralamada boş alt dizi görebiliriz.
Yönet adımına geri dönelim ve alt dizilerin özyinelemeli sıralamasını gözden geçirelim. İlk bölümden sonra, pivot 6 ise [5, 2, 3] ve [12, 7, 14, 9, 10, 11] alt dizilerimiz olur.
[5, 2, 3] alt dizisini sıralamak için, pivot olarak 3'ü seçeriz. Bölümlemeden sonra, [2, 3, 5] elde ederiz. Pivotun solundaki alt dizi [2], pivotun sağındaki alt dizi [5] gibi, yinelediğimiz zamanki temel durumdur.
[12, 7, 14, 9, 10, 11] alt dizisini sıralamak için pivot olarak 11'i seçiyoruz. Bölümlemeden sonra, pivotun solunda [7, 9, 10] ve sağında [14, 12] var. Ardından alt diziler sıralanır, [7, 9, 10], ardından 11 ve ardından [12, 14] ile sonuçlanır.
İşte hızlı sıralama algoritması böyle çalışır. Mavi renkli dizi konumları önceki özyinelemeli çağrılarda pivot olmuştur ve bu nedenle bu konumlardaki değerler tekrar incelenmeyecek veya taşınmayacaktır:
Hızlı sıralama kullanarak bir diziyi sıralamanın beş adımını gösteren bir şema.
  1. Dizi, p indeksi ilk elemanı ve r indeksi son elemanı gösterecek şekilde [9, 7, 5, 11, 12, 2, 14, 3, 10, 6] elemanları ile başlar.
  2. Dizi elemanları şimdi [5, 2, 3, 6, 12, 7, 14, 9, 10, 11] olarak sıralanmıştır. Dizinin şimdi 6 değerini içeren dördüncü öğeyi gösteren bir q indeksi vardır.
  3. Dizi elemanları [2, 3, 5, 6, 7, 9, 10, 11, 14, 12] şeklinde hala sıralanmamıştır. Dizinin artık p, q ve r adında birden çok indeksi var. İlk p birinci elemana, ilk q ikinci elemana, ilk r üçüncü elemana işaret eder. İkinci p beşinci öğeyi, ikinci q sekizinci öğeyi ve ikinci p son öğeyi gösterir.
  4. Dizi elemanları şimdi [2, 3, 5, 6, 7, 9, 10, 11, 12, 14] olarak sıralanmıştır. İlk p ve r çifti birinci elemanda, ikinci p ve r çifti üçüncü elemandadır. Üçüncü p beşinci elemanı, a q ve üçüncü r yedinci elemanını gösterir. Dördüncü p ve a q noktası dokuzuncu elemanda ve dördüncü r son elemandadır.
  5. Dizi elemanları hâlâ [2, 3, 5, 6, 7, 9, 10, 11, 12, 14] olarak sıralıdır. İlk p beşinci öğeyi, ilk q ve ilk r noktası altıncı öğeyi gösterir. Bir p ve r çifti son elemana işaret etmektedir.
  6. Dizi elemanları hala [2, 3, 5, 6, 7, 9, 10, 11, 12, 14] olarak sıralıdır. Bir p ve r çifti de beşinci elemana işaret eder.

Bu içerik Dartmouth Bilgisayar Bilimleri öğretim görevlileri Thomas Cormen ve Devin Balkcom ile Khan Academy bilgisayar bölümü içeriklerini hazırlayan takımın işbirliği ile hazırlanmıştır. İçerik CC-BY-NC-SA lisanslıdır.

Tartışmaya katılmak ister misiniz?

Henüz gönderi yok.
İngilizce biliyor musunuz? Khan Academy'nin İngilizce sitesinde neler olduğunu görmek için buraya tıklayın.