Hızlı sıralama - Quicksort

Hızlı sıralama
Hızlı sıralama anim.gif'i sıralama
Hızlı sıralama algoritmasının animasyonlu görselleştirmesi. Yatay çizgiler pivot değerlerdir.
Sınıf sıralama algoritması
En kötü durum performansı
En iyi durum performansı (basit bölüm)
veya (üç yollu bölüm ve eşit tuşlar)
Ortalama performans
En kötü durum alanı karmaşıklığı yardımcı (saf) yardımcı (Hoare 1962)

Quicksort , yerinde bir sıralama algoritmasıdır . İngiliz bilgisayar bilimcisi Tony Hoare tarafından 1959'da geliştirilen ve 1961'de yayınlanan bu algoritma, sıralama için hala yaygın olarak kullanılan bir algoritmadır. İyi uygulandığında, merge sort'dan biraz daha hızlı ve heapsort'tan yaklaşık iki veya üç kat daha hızlı olabilir .

Quicksort, bir böl ve yönet algoritmasıdır . Diziden bir 'pivot' öğesi seçerek ve diğer öğeleri pivottan küçük veya büyük olmalarına göre iki alt diziye bölerek çalışır. Bu nedenle bazen bölme-değişim sıralaması olarak adlandırılır . Alt diziler daha sonra özyinelemeli olarak sıralanır . Bu , sıralamayı gerçekleştirmek için az miktarda ek bellek gerektirerek yerinde yapılabilir .

Quicksort bir karşılaştırmalı sıralamadır , yani "küçüktür" ilişkisinin (resmi olarak toplam düzen ) tanımlandığı herhangi bir türdeki öğeleri sıralayabilir . Quicksort'un verimli uygulamaları kararlı bir sıralama değildir , yani eşit sıralamalı öğelerin göreli sırası korunmaz.

Quicksort'un matematiksel analizi , ortalama olarak , algoritmanın n öğeyi sıralamak için O ( n  log  n ) karşılaştırması aldığını gösterir . En kötü durumda O( n 2 ) karşılaştırması yapar.

Tarih

Hızlı sıralama algoritması 1959'da Tony Hoare tarafından Moskova Devlet Üniversitesi'nde misafir öğrenciyken geliştirildi . O sırada Hoare, Ulusal Fizik Laboratuvarı için bir makine çevirisi projesi üzerinde çalışıyordu . Çeviri sürecinin bir parçası olarak, Rusça cümlelerdeki kelimeleri manyetik bantta alfabetik olarak sıralanmış bir Rusça-İngilizce sözlükte aramadan önce sıralamaya ihtiyacı vardı . İlk fikrinin, eklemeli sıralamanın yavaş olacağını fark ettikten sonra , yeni bir fikir buldu. Bölüm bölümünü Mercury Autocode'da yazdı, ancak sıralanmamış bölümlerin listesiyle uğraşmakta sorun yaşadı. İngiltere'ye döndüğünde Shellsort için kod yazması istendi . Hoare patronuna daha hızlı bir algoritma bildiğinden bahsetti ve patronu bilmediğine altı peni bahse girdi. Patronu sonunda bahsi kaybettiğini kabul etti. Daha sonra Hoare öğrendik ALGOL ve kod yayınlamak sağladı Özyinelemeyi yapmak kabiliyeti Association for Computing Machinery Haberleşme , zamanın önde gelen bilgisayar bilim dergisinde.

Quicksort yaygın bir şekilde benimsendi ve örneğin Unix'te varsayılan kitaplık sıralama alt yordamı olarak göründü . Bu nedenle, adını C standart kitaplık alt yordamı qsort'a ve Java'nın referans uygulamasında verdi .

Robert Sedgewick'in 1975'teki doktora tezi, Quicksort çalışmasında bir dönüm noktası olarak kabul edilir; burada , Samplesort , Van Emden tarafından uyarlanabilir bölümleme ve beklenen sayıda karşılaştırma ve karşılaştırmanın türetilmesi dahil olmak üzere çeşitli pivot seçim şemalarının analizi ile ilgili birçok açık sorunu çözmüştür. takaslar. Jon Bentley ve Doug McIlroy , eşit öğelerle başa çıkmak için bir teknik ve dokuz öğenin bir örneğinin üçlü gruplara ve ardından medyanının ortancasının bölündüğü, dokuzlu psödomedyan olarak bilinen bir pivot şeması da dahil olmak üzere, programlama kitaplıklarında kullanım için çeşitli iyileştirmeler içeriyordu . üç gruptan üç medyan seçilir. Bentley, Nico Lomuto'ya atfedilen Programming Pearls adlı kitabında daha basit ve kompakt bir bölümleme şemasını tanımladı. Daha sonra Bentley, Hoare'nin versiyonunu yıllarca kullandığını ama asla tam olarak anlamadığını ancak Lomuto'nun versiyonunun doğru olduğunu kanıtlayacak kadar basit olduğunu yazdı. Bentley, aynı denemede Quicksort'u "şimdiye kadar yazdığım en güzel kod" olarak tanımladı. Lomuto'nun bölümleme şeması ayrıca Algoritmalara Giriş ders kitabı tarafından popüler hale getirildi, ancak Hoare'nin şemasından daha düşük olmasına rağmen, ortalama olarak üç kat daha fazla takas yapar ve tüm öğeler eşit olduğunda O ( n 2 ) çalışma zamanına düşer .

2009'da Vladimir Yaroslavskiy, bir yerine iki pivot kullanan yeni bir Quicksort uygulaması önerdi. Java çekirdek kitaplığı posta listelerinde, yeni algoritmasının, o zamanlar Bentley ve McIlroy'un klasik Quicksort'un yaygın olarak kullanılan ve dikkatle ayarlanmış varyantına dayanan çalışma zamanı kitaplığının sıralama yönteminden üstün olduğunu iddia eden bir tartışma başlattı. Yaroslavskiy'in Quicksort'u, kapsamlı deneysel performans testlerinden sonra Oracle'ın Java 7 çalışma zamanı kitaplığında yeni varsayılan sıralama algoritması olarak seçildi.

algoritma

Rastgele bir sayı kümesinde hızlı sıralamanın tam örneği. Gölgeli eleman pivottur. Her zaman bölümün son öğesi olarak seçilir. Ancak, bu şekilde her zaman bölümdeki son öğeyi pivot olarak seçmek, zaten sıralanmış dizilerde veya aynı öğelerin dizilerinde düşük performansa ( O ( n 2 ) ) neden olur . Sıralanmış / özdeş öğelerin alt dizileri, büyük bir kümede bir sıralama prosedürünün sonuna doğru çok fazla kırpıldığından, pivotu orta öğe olarak seçen hızlı sıralama algoritmasının sürümleri, bu şemada açıklanan algoritmadan çok daha hızlı çalışır. büyük sayılar kümesi.

Quicksort, bir bölümleme yordamına dayalı olarak bir diziyi sıralamak için bir tür böl ve yönet algoritmasıdır ; bu bölümlemenin ayrıntıları biraz değişebilir, bu nedenle hızlı sıralama gerçekten yakından ilişkili bir algoritmalar ailesidir. En az iki elemanlı bir aralığa uygulandığında, bölümleme, birinci alt aralığın hiçbir elemanı ikinci alt aralığın herhangi bir elemanından daha büyük olmayacak şekilde, ardışık iki boş olmayan alt aralığa bölünme üretir. Bu bölümü uyguladıktan sonra, hızlı sıralama daha sonra alt aralıkları özyinelemeli olarak sıralar, muhtemelen bu noktada zaten son konumunda olduğu bilinen bölme noktasındaki bir öğeyi onlardan hariç tuttuktan sonra. Özyinelemeli doğası nedeniyle, hızlı sıralama (bölme rutini gibi), nihai hedef tam bir diziyi sıralamak olsa bile, daha büyük bir dizi içindeki bir aralık için çağrılabilir olacak şekilde formüle edilmelidir. Yerinde hızlı sıralama için adımlar şunlardır:

  1. Aralık ikiden az öğeye sahipse, yapacak bir şey olmadığı için hemen geri dönün. Muhtemelen diğer çok kısa uzunluklar için özel amaçlı bir sıralama yöntemi uygulanır ve bu adımların geri kalanı atlanır.
  2. Aksi takdirde , aralıkta oluşan, pivot adı verilen bir değer seçin (kesin seçim şekli, bölümleme rutinine bağlıdır ve rastgelelik içerebilir).
  3. Aralığı bölümlere ayırın: bir bölme noktası belirlerken öğelerini yeniden sıralayın, böylece pivottan daha küçük değerlere sahip tüm öğeler bölmeden önce gelirken, pivottan daha büyük değerlere sahip tüm öğeler ondan sonra gelir; pivota eşit olan elemanlar her iki yöne de gidebilir. Pivotun en az bir örneği mevcut olduğundan, çoğu bölme rutini, bölme noktasında biten değerin pivota eşit olmasını ve şimdi son konumunda olmasını sağlar (ancak hızlı sıralamanın sonlandırılması buna bağlı değildir, orijinalinden kesinlikle daha küçük alt aralıklar üretildiği sürece).
  4. Bölme noktasına kadar olan alt aralığa ve ondan sonraki alt aralığa hızlı sıralamayı yinelemeli olarak uygulayın, muhtemelen her iki aralıktan da bölme noktasındaki pivota eşit öğeyi hariç tutun. (Bölme, tüm öğelerin pivota eşit olduğu bilinen sınırın yakınında muhtemelen daha büyük bir alt aralık üretiyorsa, bunlar da hariç tutulabilir.)

Bölüm rutini seçimi (pivot seçimi dahil) ve yukarıda tam olarak belirtilmeyen diğer ayrıntılar, muhtemelen belirli girdi dizileri için büyük ölçüde algoritmanın performansını etkileyebilir. Hızlı sıralamanın etkinliğini tartışırken, bu nedenle öncelikle bu seçenekleri belirlemek gerekir. Burada iki özel bölümleme yönteminden bahsediyoruz.

Lomuto bölme şeması

Bu şema Nico Lomuto'ya atfedilir ve Bentley tarafından Programming Pearls and Cormen et al. Algoritmalara Giriş adlı kitaplarında . Bu şema, tipik olarak dizideki son öğe olan bir pivot seçer. Algoritma indeksi muhafaza i başka bir göstergesi kullanılarak dizi tarar j en elemanlarının bu lo ile i-1 (dahil) daha az eksen ve en elemanlarından daha vardır i ile j (içinde) eşit ya da daha büyük bir eksen. Bu şema daha kompakt ve anlaşılması kolay olduğundan, örneğin tüm elemanlar eşit olduğunda Hoare'nin orijinal şemasından daha az verimli olmasına rağmen, giriş materyalinde sıklıkla kullanılır. Bu şema , dizi zaten sırayla olduğunda O ( n 2 ) değerine düşer . Pivot seçme, eşit öğelerle uğraşma, küçük diziler için Ekleme sıralama gibi diğer sıralama algoritmalarını kullanma gibi çeşitli yollar dahil olmak üzere performansı artırmak için önerilen çeşitli varyantlar vardır . Gelen pseudocode , bir quicksort de sıralar elemanlarının lo aracılığıyla hi bir dizi arasında (dahili) A olarak da ifade edilebilir:

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  // If indices are in correct order
  if lo >= 0 && hi >= 0 && lo < hi then 
    // Partition array and get pivot index
    p := partition(A, lo, hi) 
      
    // Sort the two partitions
    quicksort(A, lo, p - 1) // Left side of pivot
    quicksort(A, p + 1, hi) // Right side of pivot

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  pivot := A[hi] // The pivot must be the last element

  // Pivot index
  i := lo - 1

  for j := lo to hi do 
    // If the current element is less than or equal to the pivot
    if A[j] <= pivot then 
      // Move the pivot index forward
      i := i + 1

      // Swap the current element with the element at the pivot
      swap A[i] with A[j] 
  return i // the pivot index

Tüm diziyi sıralama, quicksort(A, 0, length(A) - 1) ile gerçekleştirilir .

Hoare bölme şeması

Hoare'nin bölüm şemasını kullanan Quicksort'un animasyonlu bir gösterimi. Kırmızı anahatlar sol ve sağ işaretçilerin ( ive jsırasıyla) konumlarını, siyah anahatlar sıralanmış öğelerin konumlarını gösterir ve doldurulmuş siyah kare ( pivot) ile karşılaştırılan değeri gösterir .

Tony Hoare tarafından açıklanan orijinal bölümleme şeması, bölümlenen dizinin her iki ucundan başlayan ve ardından bir ters çevirme algılayana kadar birbirlerine doğru hareket eden iki işaretçi (aralık içindeki dizinler) kullanır: biri sınırdan daha büyük olan bir çift öğe. (Hoare'nin pivot değeri için kullandığı terimler) birinci işaretçide ve ikinci işaretçide sınırdan bir eksik; bu noktada ilk işaretçi hala ikinciden önceyse, bu öğeler birbirine göre yanlış sıradadır ve daha sonra değiştirilirler. Bundan sonra işaretçiler içeri doğru hareket ettirilir ve bir ters çevirme arayışı tekrarlanır; sonunda işaretçiler kesiştiğinde (ikinciden sonraki ilk noktalar), değişim yapılmaz; çapraz işaretçiler arasındaki bölme noktası ile geçerli bir bölüm bulunur (kesinlikle çapraz işaretçiler arasında olabilecek herhangi bir giriş, pivot değerine eşittir ve oluşturulan her iki alt aralıktan hariç tutulabilir). Bu formülasyonla, bir alt aralığın, algoritmanın ilerlemesini önleyecek şekilde tüm orijinal aralık olduğu ortaya çıkabilir. Bu nedenle Hoare, sonunda, (hala orijinal konumunda olan) pivot elemanı içeren alt aralığın, (gerekirse) en yakın alt aralık elemanı ile değiştirildikten sonra, bu pivot hariç tutularak boyutunun küçültülebileceğini şart koşar. ayrılık; böylece hızlı sıralamanın sonlandırılması sağlanır.

Bu orijinal açıklamaya göre, uygulamalar genellikle küçük ama önemli değişiklikler yapar. Özellikle, aşağıda sunulan şema, bir tersine çevirme için adaylar arasında pivota eşit öğeleri içerir (bu nedenle, sırasıyla "büyüktür" veya "küçüktür" yerine "büyük veya eşittir" ve "küçüktür veya eşittir" testleri kullanılır; çünkü formülasyon kullanır do ... ederken ziyade tekrar ... kadar hangi aslında) sıkı bir karşılaştırma operatörleri kullanılarak yansır. Sınıra eşit öğeleri değiş tokuş etmek için bir neden olmamasına rağmen, bu değişiklik, işaretçilerin kendileri üzerindeki testlerin atlanmasına olanak tanır, aksi takdirde aralık dışına çıkmamalarını sağlamak için gereklidir. Aslında, aralıkta pivot değerinin en az bir örneği mevcut olduğundan, kapsayıcı bir test kullanılırsa her iki işaretçinin ilk ilerlemesi bu örneği geçemez; bir değişim gerçekleştirildikten sonra, bu değiş tokuş edilen öğelerin ikisi de artık onları bulan işaretçinin kesinlikle önündedir ve bu işaretçinin kaçmasını önler. (Sonuncusu, kullanılan testten bağımsız olarak doğrudur, bu nedenle kapsayıcı testi yalnızca ilk inversiyon ararken kullanmak mümkün olacaktır. Bununla birlikte, baştan sona kapsayıcı bir test kullanmak, içindeki tüm öğeler olduğunda ortaya yakın bir bölmenin bulunmasını sağlar. aralık eşittir, bu da birçok eşit öğeye sahip dizileri sıralamak için önemli bir verimlilik kazancı sağlar.) İlerlemeyen bir ayırma üretme riskinden Hoare tarafından açıklanandan farklı bir şekilde kaçınılır. Böyle bir ayırma, yalnızca, her iki işaretçi de ilk yinelemede pivot öğeye ilerlerken (daha sonra kesiştikleri kabul edilir ve hiçbir değişim gerçekleşmez) hiçbir ters çevirme bulunmadığında sonuçlanabilir. Döndürülen bölme, ikinci işaretçinin son konumundan sonradır, bu nedenle kaçınılması gereken durum, pivotun aralığın son öğesi olduğu ve diğerlerinin ondan daha küçük olduğu durumdur. Bu nedenle, pivot seçimi son öğeden kaçınmalıdır (Hoare'nin açıklamasında, aralıktaki herhangi bir öğe olabilir); bu, işlev kullanılarak orta konumun aşağı yuvarlanmasıyla burada yapılır floor. Bu, Hoare bölme şemasının bir uygulamasının doğruluğu argümanının incelikli olabileceğini ve yanlış anlamanın kolay olduğunu göstermektedir.

In pseudocode ,

// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is 
  if lo >= 0 && hi >= 0 && lo < hi then
    p := partition(A, lo, hi) 
    quicksort(A, lo, p) // Note: the pivot is now included
    quicksort(A, p + 1, hi) 

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at 
    // the left index is less than the pivot 
    do i := i + 1 while A[i] < pivot 
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot 
    do j := j - 1 while A[j] > pivot 

    // If the indices crossed, return
    if i ≥ j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

Tüm dizi, quicksort(A, 0, length(A) - 1) ile sıralanır .

Hoare'nin planı, Lomuto'nun bölme şemasından daha verimli çünkü ortalama olarak üç kat daha az takas yapıyor. Ayrıca, belirtildiği gibi, verilen uygulama, tüm değerler eşit olduğunda bile, Lomuto'nun şemasında olmayan dengeli bir bölüm oluşturur. Lomuto'nun bölümleme şeması gibi, Hoare'nin bölümlemesi de , pivot ilk veya son eleman olarak seçilmişse, Quicksort'un zaten sıralanmış giriş için O ( n 2 ) değerine düşmesine neden olur . Bununla birlikte, ortadaki öğe pivot olarak kullanıldığında, eşit büyüklükteki bölümlerde (neredeyse) hiçbir takas ile sonuçlanmaz, bu da Quicksort'un en iyi durum davranışına yol açar, yani O ( n log( n )) . Diğerleri gibi, Hoare'nin bölümlemesi de kararlı bir sıralama oluşturmaz. Bu şemada, pivot ve pivota eşit elemanlar, bir bölümleme adımından sonra bölümün herhangi bir yerinde son bulabileceğinden ve bir tek elemanlı bölmeye özyineleme ile ulaşılır. Ana algoritmanın yinelendiği sonraki iki segment (lo..p) (eleman ≤ pivot) ve (p+1..hi) (eleman ≥ pivot) (lo..p-1) ve (p)'dir. +1..hi) Lomuto'nun şemasındaki gibi.

Uygulama sorunları

Pivot seçimi

Hızlı sıralamanın çok erken sürümlerinde, bölümün en soldaki öğesi genellikle pivot öğesi olarak seçilirdi. Ne yazık ki, bu, oldukça yaygın bir kullanım durumu olan zaten sıralanmış dizilerde en kötü durum davranışına neden olur. Sorun, pivot için rastgele bir dizin seçerek, bölümün orta dizinini seçerek veya (özellikle daha uzun bölümler için) pivot için bölümün ilk, orta ve son öğesinin medyanını seçerek (önerildiği gibi ) kolayca çözüldü . Sedgewick'e göre ). Bu "üçte ortanca" kuralı, sıralanmış (veya ters sıralanmış) girdi durumunu sayar ve en uygun pivotun (gerçek medyan) sıralaması hakkında hiçbir bilgi olmadığında herhangi bir tek öğeyi seçmekten daha iyi bir tahmin verir. girdi malum.

Lomuto bölümü için ortanca üç kod parçacığı:

mid := ⌊(lo + hi) / 2⌋
if A[mid] < A[lo]
    swap A[lo] with A[mid]
if A[hi] < A[lo]
    swap A[lo] with A[hi]
if A[mid] < A[hi]
    swap A[mid] with A[hi]
pivot := A[hi]

A[hi]Önce bir medyanı koyar , ardından A[hi]yukarıda sunulan temel bir algoritmada olduğu gibi bir pivot için bu yeni değeri kullanılır.

Spesifik olarak, n öğeyi rastgele pivot seçimiyle sıralamak için gereken beklenen karşılaştırma sayısı (bkz. § Rastgele hızlı sıralama analizi ) 1.386 n log n'dir . Ortalama üç eksen etrafında dönme , beklenen takas sayısında yüzde üçlük bir artış pahasına bunu C n , 2 ≈ 1.188 n log n değerine düşürür . Daha büyük diziler için daha da güçlü bir döner kuralı, seçmektir ninther , bir özyinelemeli medyan-of-üç (MO3), olarak tanımlanır

dokuzuncu( a ) = medyan(Mo3(birinci) 1/3arasında bir ), MO3 (orta1/3arasında bir ), MO3 (nihai1/3arasında bir ))

Bir pivot elemanının seçilmesi, tamsayı taşmasının varlığı nedeniyle de karmaşıktır . Sıralanan alt dizinin sınır indeksleri yeterince büyükse, orta indeks için naif ifade ( lo + hi )/2 , taşmaya neden olacak ve geçersiz bir pivot indeks sağlayacaktır. Ortadaki elemanı indekslemek için, örneğin lo + ( hilo )/2 kullanılarak , daha karmaşık aritmetik pahasına bunun üstesinden gelinebilir . Pivot elemanı seçmenin diğer bazı yöntemlerinde de benzer sorunlar ortaya çıkar.

Tekrarlanan öğeler

Yukarıda açıklanan Lomuto bölümleme şeması gibi bir bölümleme algoritmasıyla (iyi pivot değerleri seçse bile), hızlı sıralama, birçok tekrarlanan öğe içeren girdiler için düşük performans sergiler. Sorun, tüm girdi öğeleri eşit olduğunda açıkça görülür: her özyinelemede, sol bölüm boştur (hiçbir giriş değeri pivottan daha az değildir) ve sağ bölüm yalnızca bir öğe tarafından azalmıştır (pivot kaldırılmıştır). Sonuç olarak, Lomuto bölme şeması , eşit değerler dizisini sıralamak için ikinci dereceden zaman alır . Bununla birlikte, Hoare bölümleme şeması gibi bir bölümleme algoritması ile, tekrarlanan öğeler genellikle daha iyi bölümleme ile sonuçlanır ve pivota eşit öğelerin gereksiz takasları gerçekleşebilse de, tekrarlanan öğelerin sayısı arttıkça çalışma süresi genellikle azalır (bellek önbelleği ile) takas yükünün azaltılması). Tüm öğelerin eşit olduğu durumda, Hoare bölümleme şeması öğeleri gereksiz yere değiştirir, ancak yukarıdaki Hoare bölümleme bölümünde belirtildiği gibi bölümlemenin kendisi en iyi durumdur.

Lomuto bölme şeması problemini (bazen Hollanda ulusal bayrak problemi olarak da adlandırılır) çözmek için , değerleri üç gruba ayıran alternatif bir doğrusal zaman bölme rutini kullanılabilir: pivottan küçük değerler, pivota eşit değerler ve daha büyük değerler pivottan daha. (Bentley ve McIlroy bu bir "şişman bölüm" diyoruz ve zaten hayata geçirildi qsort ait Sürüm 7 Unix .) Değerleri zaten sıralanır pivot eşit, yani sadece yinelemeli gerekir Küçüktür ve bölümleri büyüktür sıralanmış. Sözde kodda, hızlı sıralama algoritması olur

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi)  // note: multiple return values
        quicksort(A, lo, left - 1)
        quicksort(A, right + 1, hi)

partitionİlk ( 'en soldaki') ve orta bölümünün son ( 'en sağdaki') öğeye için algoritma döner endeksleri. Bölümün her öğesi eşittir pve bu nedenle sıralanır. Sonuç olarak, bölümün öğelerinin özyinelemeli çağrılara dahil edilmesi gerekmez quicksort.

Algoritma için en iyi durum, tüm elemanlar eşit olduğunda (veya küçük bir kn eleman kümesinden seçildiğinde ) ortaya çıkar. Tüm öğelerin eşit olması durumunda, değiştirilmiş hızlı sıralama boş alt diziler üzerinde yalnızca iki özyinelemeli çağrı gerçekleştirir ve böylece doğrusal zamanda tamamlanır (alt rutinin doğrusal zamandan partitiondaha uzun sürmediği varsayılırsa ).

Optimizasyonlar

Yine Sedgewick tarafından önerilen ve pratikte yaygın olarak kullanılan diğer iki önemli optimizasyon şunlardır:

  • En fazla O (log n ) boşluğunun kullanıldığından emin olmak için , önce bölümün daha küçük tarafında tekrar edin, ardından diğerine tekrarlamak için bir kuyruk çağrısı kullanın veya parametreleri artık sıralanan daha küçük tarafı içermeyecek şekilde güncelleyin ve daha büyük tarafı sıralamak için yineleyin.
  • Öğe sayısı belirli bir eşiğin (belki on öğe) altında olduğunda, bu tür küçük dizilerde daha az takas, karşılaştırma veya diğer işlemler gerçekleştiren eklemeli sıralama gibi yinelemeli olmayan bir sıralama algoritmasına geçin . İdeal 'eşik', belirli uygulamanın ayrıntılarına göre değişecektir.
  • Önceki optimizasyonun daha eski bir çeşidi: eleman sayısı k eşiğinden az olduğunda , basitçe durun; daha sonra tüm dizi işlendikten sonra, üzerinde eklemeli sıralama gerçekleştirin. Özyinelemeyi erken durdurmak, diziyi k- sıralı bırakır , yani her öğe son sıralanmış konumundan en fazla k konum uzaktadır. Bu durumda, eklemeli sıralama, k sabitse doğrusal olan sıralamayı bitirmek için O ( kn ) zaman alır . "Birçok küçük tür" optimizasyonu ile karşılaştırıldığında, bu sürüm daha az talimat yürütebilir, ancak modern bilgisayarlarda önbellek belleklerinin optimal olmayan kullanımını sağlar .

paralelleştirme

Quicksort'un böl ve yönet formülü, onu görev paralelliğini kullanarak paralelleştirmeye uygun hale getirir . Bölümleme adımı, bölümlenmiş dizinin kendi bölümündeki her dizi öğesi için bir dizin hesaplamak üzere bir paralel önek toplamı algoritmasının kullanılmasıyla gerçekleştirilir . n boyutunda bir dizi verildiğinde , bölümleme adımı O( n ) işini O (log n ) zamanında gerçekleştirir ve O( n ) ek karalama alanı gerektirir. Dizi bölümlendikten sonra, iki bölüm yinelemeli olarak paralel olarak sıralanabilir. Pivotların ideal bir seçim varsayarak, paralel quicksort boyutu, bir dizi sıralar n de (O n log n )O (log 2 N ) defasında O ( n ) ek alan.

Quicksort, verimli paralelleştirmesini zorlaştıran birleştirme sıralama gibi alternatif sıralama algoritmalarıyla karşılaştırıldığında bazı dezavantajlara sahiptir . Quicksort'un böl ve yönet ağacının derinliği, algoritmanın ölçeklenebilirliğini doğrudan etkiler ve bu derinlik, algoritmanın pivot seçimine büyük ölçüde bağlıdır. Ek olarak, bölümleme adımını yerinde verimli bir şekilde paralel hale getirmek zordur. Karalama alanı kullanımı, bölümleme adımını basitleştirir, ancak algoritmanın bellek ayak izini ve sabit genel giderleri artırır.

Diğer daha karmaşık paralel sıralama algoritmaları daha da iyi zaman sınırları sağlayabilir. Örneğin, 1991 David Powers paralelleştirilmiş quicksort (ve ilgili tarif edilen kök tür çalışabilen) O (log n ) bir zamanı CRCW (eşzamanlı okuma, yazma işlemi) PAAM ile (rastgele erişim makinesi paralel) n ile işlemci bölümlemeyi dolaylı olarak gerçekleştirir.

Resmi analiz

En kötü durum analizi

En dengesiz bölümleme, bölümleme yordamı tarafından döndürülen alt listelerden biri n -1 boyutunda olduğunda oluşur . Bu, pivot, listedeki en küçük veya en büyük eleman olursa veya bazı uygulamalarda (örneğin, yukarıda açıklandığı gibi Lomuto bölme şeması) tüm elemanlar eşit olduğunda meydana gelebilir.

Bu, her bölümde tekrar tekrar oluyorsa, her özyinelemeli çağrı, önceki listeden bir küçük boyutlu bir liste işler. Sonuç olarak, 1 boyutlu bir listeye ulaşmadan önce n − 1 iç içe çağrı yapabiliriz . Bu, çağrı ağacının n − 1 iç içe çağrılardan oluşan doğrusal bir zincir olduğu anlamına gelir . İ inci çağrı yapar Ç ( n - i ) bölümü yapacak işi ve böylece sürer quicksort bu durumda, O ( n 2 ) zamanı.

En iyi durum analizi

En dengeli durumda, her bölme işlemi yaptığımızda listeyi neredeyse eşit iki parçaya böleriz. Bu, her özyinelemeli çağrının yarı boyutunda bir listeyi işlediği anlamına gelir. Sonuç olarak, biz sadece yapabilirsiniz log 2 n biz derinliği olduğu bu araçlar boyutta 1. listesini ulaşmadan iç içe aramaları çağrı ağacının olduğunu log 2 n . Ancak, çağrı ağacının aynı düzeyindeki hiçbir iki çağrı, orijinal listenin aynı bölümünü işlemez; bu nedenle, her çağrı düzeyi hep birlikte yalnızca O ( n ) zamana ihtiyaç duyar (her çağrının sabit bir ek yükü vardır, ancak her düzeyde yalnızca O ( n ) çağrı olduğundan, bu O ( n ) faktörüne dahil edilir). Sonuç, algoritmanın yalnızca O ( n log n ) zamanını kullanmasıdır.

Ortalama durum analizi

Bir dizi sıralamak için n farklı unsurların, çabuk alır Ç ( n log n ) beklenti zaman, tüm üzerinden ortalama n ! n elementin eşit olasılıklı permütasyonları . Quicksort'un işleyişine dair farklı anlayışlar sağlayan bu iddianın üç ortak kanıtını burada listeliyoruz.

Yüzdelikleri kullanma

Her pivot orta yüzde 50'lik bir yerde, yani yüzde 25 ile yüzde 75 arasında bir sıralamaya sahipse , öğeleri her iki tarafta en az %25 ve en fazla %75 olacak şekilde böler. Bu tür pivotları tutarlı bir şekilde seçebilseydik, listeyi çoğu zaman 1 boyutlu listelere ulaşmadan önce bölmek zorunda kalırdık ve bir O ( n log n ) algoritması verirdik.

Girdi rastgele bir permütasyon olduğunda, pivotun rastgele bir sıralaması vardır ve bu nedenle yüzde 50'nin ortasında olması garanti edilmez. Bununla birlikte, rastgele bir permütasyondan başladığımızda, her özyinelemeli çağrıda, pivotun listesinde rastgele bir sıralaması vardır ve bu nedenle, zamanın yaklaşık yüzde 50'sinde ortadadır. Bu yeterince iyi. Bir madeni paranın atıldığını hayal edin: tura, pivotun sıralamasının yüzde 50'nin ortasında olduğu anlamına gelir, kuyruk, olmadığı anlamına gelir. Şimdi madeni paranın k tura gelene kadar ters çevrildiğini hayal edin . Bu uzun zaman alabilse de, ortalama olarak sadece 2 k atış gereklidir ve madeni paranın 100 k atıştan sonra k tura gelmemesi olasılığı oldukça düşüktür (bu, Chernoff sınırları kullanılarak kesinleştirilebilir ). Aynı argümana göre, Quicksort'un özyinelemesi ortalama olarak yalnızca . Ancak ortalama çağrı derinliği O (log n ) ise ve çağrı ağacının her seviyesi en fazla n öğeyi işlerse, ortalama olarak yapılan toplam iş miktarı O ( n log n ) çarpımıdır . Algoritma, pivotun orta yarıda olduğunu doğrulamak zorunda değildir - eğer ona zamanın herhangi bir sabit kısmına çarparsak, bu istenen karmaşıklık için yeterlidir.

Yinelemeleri kullanma

Alternatif bir yaklaşım, n boyutundaki bir listeyi sıralamak için gereken süre olan T ( n ) faktörü için bir yineleme ilişkisi kurmaktır . En dengesiz durumda, tek bir hızlı sıralama çağrısı O ( n ) çalışmasına ek olarak 0 ve n -1 boyutundaki listelerde iki özyinelemeli çağrı içerir , dolayısıyla yineleme ilişkisi şöyledir:

Bu aynı ilişkidir sıralama yerleştirilmesi ve sıralama seçimi ve en kötü durum için çözer T ( n =) O ( n, 2 ) .

En dengeli durumda, tek bir hızlı sıralama çağrısı O ( n ) işi artı n /2 boyutundaki listelerde iki özyinelemeli çağrı içerir , dolayısıyla yineleme ilişkisi şöyledir:

Böl-böl nüks için ana teoremi bize bu T ( n ) = O ( n, log n ) .

O ( n log n ) beklenen zaman karmaşıklığının resmi bir kanıtının ana hatları aşağıdadır. Yinelemeler, doğrusal zaman ön ve son işleme ile ele alınabileceğinden veya analiz edilenden daha kolay kabul edilen durumlar olduğundan, yineleme olmadığını varsayın. Girdi rastgele bir permütasyon olduğunda, pivot sıralaması 0 ile n − 1 arasında tek tip rastgeledir . Daha sonra, bölümün elde edilen kısımları i ve n - i - 1 boyutlarına sahiptir ve i 0'dan n - 1'e kadar düzgün rasgeledir . Böylece, tüm olası bölmelerin ortalaması alınır ve bölüm için karşılaştırma sayısının n - 1 olduğuna dikkat edilirse, giriş dizisinin tüm permütasyonları üzerindeki ortalama karşılaştırma sayısı, yineleme ilişkisi çözülerek doğru bir şekilde tahmin edilebilir:

Yinelemeyi çözmek C ( n ) = 2 n ln n ≈ 1.39 n log 2 n'yi verir .

Bu, hızlı sıralamanın ortalama olarak en iyi durumundan yalnızca yaklaşık %39 daha kötü performans gösterdiği anlamına gelir. Bu anlamda en iyi duruma en kötü durumdan daha yakındır. Bir karşılaştırma sıralama daha az kullanamaz günlüğüne 2 ( n !) Sıralamak için ortalama olarak karşılaştırmalar n (aynı ürün makalesinde sıralama Karşılaştırma açıklanmıştır ) ve büyük olması durumunda n , Stirling'in yaklaşım verimleri log 2 ( n !) ≈ n (log 2 n − log 2 e ) , bu nedenle hızlı sıralama ideal bir karşılaştırmalı sıralamadan çok daha kötü değildir. Bu hızlı ortalama çalışma süresi, Quicksort'un diğer sıralama algoritmaları üzerindeki pratik üstünlüğünün bir başka nedenidir.

İkili arama ağacı kullanma

Aşağıdaki ikili arama ağacı (BST), her bir hızlı sıralama uygulamasına karşılık gelir: ilk pivot, kök düğümdür; sol yarının ekseni sol alt ağacın köküdür, sağ yarının ekseni sağ alt ağacın köküdür, vb. Quicksort uygulamasının karşılaştırma sayısı, bir dizi ekleme ile BST'nin inşası sırasındaki karşılaştırmaların sayısına eşittir. Bu nedenle, rastgele hızlı sıralama için ortalama karşılaştırma sayısı, eklenen değerler rastgele bir permütasyon oluşturduğunda bir BST oluşturmanın ortalama maliyetine eşittir .

Rastgele bir permütasyon oluşturan bir dizi değerin eklenmesiyle oluşturulan bir BST düşünün . Let C BST yaratılması maliyetini belirtir. Elimizde , nerede olduğunu ifade eden bir ikili rasgele değişken olup olmadığının eklenmesi sırasında bir karşılaştırma yapılmadı .

Tarafından beklenti doğrusallığı , beklenen değer arasında C olan .

i ve j < i'yi düzeltin . Değerler sıralandıktan sonra j +1 aralıklarını tanımlar . Çekirdek yapı gözlem olmasıdır karşılaştırılır algoritma ancak ve ancak bitişik iki aralıklı biri içine düşen .

Rastgele bir permütasyon olduğu için, aynı zamanda bir rastgele permütasyon olduğuna dikkat edin, bu nedenle bitişik olan olasılık tam olarak .

Kısa bir hesaplama ile bitiriyoruz:

Uzay karmaşıklığı

Quicksort tarafından kullanılan alan, kullanılan sürüme bağlıdır.

Quicksort'un yerinde sürümü , aşağıdaki stratejiler kullanılarak dikkatlice uygulandığında, en kötü durumda bile , O (log n ) uzay karmaşıklığına sahiptir .

  • Yerinde bölümleme kullanılır. Bu kararsız bölüm, O (1) alanı gerektirir .
  • Bölümlemeden sonra, en fazla O (log n ) boşluk gerektiren, en az öğeye sahip bölüm ilk olarak (yinelemeli olarak) sıralanır . Ardından diğer bölüm, çağrı yığınına eklenmeyen kuyruk özyineleme veya yineleme kullanılarak sıralanır . Bu fikir, yukarıda tartışıldığı gibi, R. Sedgewick tarafından tanımlanmıştır ve yığın derinliğini O (log n ) ile sınırlı tutar .

Yerinde ve kararsız bölümlemeli Quicksort, herhangi bir özyinelemeli arama yapmadan önce yalnızca sabit ek alan kullanır. Quicksort, her iç içe geçmiş yinelemeli çağrı için sabit miktarda bilgi depolamalıdır. En iyi durum en fazla O (log n ) iç içe özyinelemeli çağrılar yaptığından, O (log n ) alanı kullanır . Bununla birlikte, Sedgewick'in özyinelemeli çağrıları sınırlama hilesi olmadan, en kötü durumda hızlı sıralama, O ( n ) iç içe özyinelemeli çağrılar yapabilir ve O ( n ) yardımcı alana ihtiyaç duyabilir .

Biraz karmaşıklık açısından, lo ve hi gibi değişkenler sabit boşluk kullanmazlar; Tek gereken O (log n ) bir liste halinde dizin bitlerini n öğeleri. Her yığın çerçevesinde bu tür değişkenler olduğundan, Sedgewick'in hilesini kullanan hızlı sıralama, O ((log n ) 2 ) bit boşluk gerektirir. Bu alan gereksinimi çok korkunç değildir, çünkü liste farklı öğeler içeriyorsa, en az O ( n log n ) bitlik alana ihtiyaç duyacaktır .

Quicksort'un daha az yaygın, yerinde olmayan başka bir sürümü, çalışma depolaması için O ( n ) alanı kullanır ve kararlı bir sıralama uygulayabilir. Çalışan depolama, giriş dizisinin istikrarlı bir şekilde kolayca bölümlenmesine ve ardından ardışık yinelemeli çağrılar için giriş dizisine geri kopyalanmasına olanak tanır. Sedgewick'in optimizasyonu hala uygundur.

Diğer algoritmalarla ilişkisi

Quicksort, ikili ağaç sıralamasının alan açısından optimize edilmiş bir sürümüdür . Öğeleri açık bir ağaca sırayla eklemek yerine, hızlı sıralama bunları aynı anda özyinelemeli çağrıların ima ettiği bir ağaçta düzenler. Algoritmalar tamamen aynı karşılaştırmaları yapar, ancak farklı bir sırada. Bir sıralama algoritmasının genellikle istenen bir özelliği kararlılıktır - yani, eşit olan öğelerin sırası değişmez, çok tuşlu tabloların (örneğin dizin veya klasör listeleri) sırasını doğal bir şekilde kontrol etmeye izin verir. Bu özelliğin yerinde (veya yerinde) hızlı sıralama (işaretçiler ve arabellekler için yalnızca sabit ek alan ve açık veya örtük özyinelemenin yönetimi için O (log n ) ek alanı kullanan) için bakımı zordur . İşaretçiler (örneğin listeler veya ağaçlar) veya dosyalar (etkili listeler) kullanan temsiller nedeniyle ekstra bellek içeren değişken hızlı sıralamalar için, kararlılığı korumak önemsizdir. Daha karmaşık veya diske bağlı veri yapıları, genel olarak sanal bellek veya disk kullanımını artırarak zaman maliyetini artırma eğilimindedir.

Quicksort'un en doğrudan rakibi heapsort'tur . Yığın sıralamanın çalışma süresi O ( n log n ) 'dir , ancak yığın sıralamanın ortalama çalışma süresinin genellikle yerinde hızlı sıralamadan daha yavaş olduğu kabul edilir. Bu sonuç tartışmalıdır; bazı yayınlar bunun tersini göstermektedir. Introsort , hızlı sıralamanın en kötü durum çalışma süresini önlemek için kötü bir durum algılandığında yığın sıralamaya geçen bir hızlı sıralama çeşididir.

Quicksort ayrıca başka bir O ( n log n ) sıralama algoritması olan merge sort ile rekabet eder . Mergesort bir olduğunu Sıralama kararlı standart yerinde quicksort ve HizliSiralama aksine, ve mükemmel kötü durum performansına sahiptir. Birleştirmenin ana dezavantajı, diziler üzerinde çalışırken verimli uygulamaların O ( n ) yardımcı alanı gerektirmesidir , oysa yerinde bölümleme ve kuyruk özyinelemeli hızlı sıralama varyantı yalnızca O (log n ) alanı kullanır.

Mergesort , yalnızca küçük, sabit miktarda yardımcı depolama gerektiren bağlantılı listelerde çok iyi çalışır . Hızlı sıralama, bağlantılı listeler kullanılarak kararlı bir sıralama olarak uygulanabilmesine rağmen, rastgele erişim olmadan genellikle zayıf pivot seçeneklerinden muzdarip olacaktır. Mergesort ayrıca, disk depolama veya ağa bağlı depolama gibi erişimi yavaş ortamlarda depolanan çok büyük veri kümelerinin harici olarak sıralanması için tercih edilen algoritmadır .

İki kovalı kova sıralama , hızlı sıralamaya çok benzer; bu durumda pivot, etkin bir şekilde değer aralığının ortasındaki değerdir ve bu, eşit olarak dağıtılmış girdiler için ortalama olarak iyi sonuç verir.

Seçime dayalı döndürme

Bir seçim algoritması seçtiği k numaralarının bir listesinin en küçük inci; bu, genel olarak sıralamaktan daha kolay bir problemdir. Basit ama etkili bir seçim algoritması, hızlı sıralama ile hemen hemen aynı şekilde çalışır ve buna göre hızlı seçim olarak bilinir . Aradaki fark, her iki alt listede özyinelemeli çağrılar yapmak yerine, istenen öğeyi içeren alt listede yalnızca tek bir kuyruk özyinelemeli çağrı yapmasıdır. Bu değişiklik, ortalama karmaşıklığı , seçim için en uygun olan lineer veya O ( n ) zamanına düşürür , ancak seçim algoritması en kötü durumda hala O ( n 2 ) 'dir.

Medyanların medyanı algoritması olan hızlı seçimin bir çeşidi, pivotları daha dikkatli seçerek, pivotların verilerin ortasına yakın (30. ve 70. persentiller arasında) olmasını sağlar ve böylece garantili doğrusal zaman – O ( n ) sağlar . Bu aynı pivot stratejisi, O ( n log n ) zamanla bir hızlı sıralama (medyan hızlı sıralama) varyantı oluşturmak için kullanılabilir . Bununla birlikte, pivot seçiminin ek yükü önemlidir, bu nedenle bu genellikle pratikte kullanılmaz.

Daha soyut olarak, verilen bir O ( n ) seçim algoritması, hızlı sıralamanın her adımında ideal pivotu (ortanca) bulmak için kullanabilir ve böylece O ( n log n ) çalışma süresine sahip bir sıralama algoritması üretebilir . Bu varyantın pratik uygulamaları ortalama olarak oldukça yavaştır, ancak teorik olarak ilgi çekicidir, çünkü optimal bir seçim algoritması gösterdikleri için optimal bir sıralama algoritması verebilirler.

Varyantlar

Çok eksenli hızlı sıralama

Bunun yerine tek bir pivot kullanılarak iki altdizilimlerden halinde bölünmesi, çoklu eksen quicksort (aynı zamanda multiquicksort) bir kısmı içine girişini bölmeler s kullanılarak altdizilimlerden sayısına s 1 - döner. Çift eksenli durum ( s = 3 ) Sedgewick ve diğerleri tarafından zaten 1970'lerin ortalarında düşünülürken, ortaya çıkan algoritmalar pratikte "klasik" hızlı sıralamadan daha hızlı değildi. İşlemci önbelleklerini verimli kullanmak üzere ayarlanmış, değişken sayıda pivota sahip bir çoklu hızlı sıralamanın 1999 yılındaki bir değerlendirmesi, bunun talimat sayısını yaklaşık %20 oranında artırdığını buldu, ancak simülasyon sonuçları, çok büyük girdilerde daha verimli olacağını gösterdi. 2009'da Yaroslavskiy tarafından geliştirilen çift eksenli hızlı sıralamanın bir sürümünün, ilkel dizileri sıralamak için standart algoritma olarak Java 7'de uygulamayı garanti edecek kadar hızlı olduğu ortaya çıktı ( nesne dizilerini sıralama Timsort kullanılarak yapılır ). Bu algoritmanın performans avantajının daha sonra çoğunlukla önbellek performansıyla ilgili olduğu bulundu ve deneysel sonuçlar, üç eksenli varyantın modern makinelerde daha da iyi performans gösterebileceğini gösteriyor.

Harici hızlı sıralama

Disk dosyaları için, hızlı sıralamaya benzer bölümlemeye dayalı harici bir sıralama mümkündür. Harici birleştirme sıralamasından daha yavaştır, ancak fazladan disk alanı gerektirmez. Giriş için 2, çıkış için 2 olmak üzere 4 tampon kullanılır. N = dosyadaki kayıt sayısı, B = arabellek başına kayıt sayısı ve M = N/B = dosyadaki arabellek bölümlerinin sayısı olsun. Veriler dosyanın her iki ucundan içeriye doğru okunur (ve yazılır). X, dosyanın başında başlayan segmentleri ve Y dosyanın sonunda başlayan segmentleri temsil etsin. Veriler, X ve Y okuma arabelleklerine okunur. Bir pivot kayıt seçilir ve pivot kayıt dışındaki X ve Y tamponlarındaki kayıtlar, pivot kayıtla karşılaştırmaya dayalı olarak artan sırada X yazma tamponuna ve azalan sırayla Y yazma tamponuna kopyalanır. X veya Y arabelleği doldurulduğunda, dosyaya yazılır ve sonraki X veya Y arabelleği dosyadan okunur. İşlem, tüm bölümler okunana ve bir yazma arabelleği kalana kadar devam eder. Bu arabellek bir X yazma arabelleğiyse, özet kayıt buna eklenir ve X arabelleği yazılır. Bu arabellek bir Y yazma arabelleğiyse, özet kaydı Y arabelleğine eklenir ve Y arabelleği yazılır. Bu, dosyanın bir bölüm adımını oluşturur ve dosya şimdi iki alt dosyadan oluşur. Her bir alt dosyanın başlangıç ​​ve bitiş konumları, özyineleme yoluyla bağımsız bir yığına veya ana yığına itilir/açılır. Yığın alanını O(log2(n)) ile sınırlamak için önce daha küçük olan alt dosya işlenir. Bağımsız bir yığın için, daha büyük alt dosya parametrelerini yığının üzerine itin, daha küçük alt dosyada yineleyin. Özyineleme için, önce daha küçük alt dosyada yineleme yapın, ardından daha büyük alt dosyayı işlemek için yineleyin. Bir alt dosya 4 B kaydına eşit veya daha küçük olduğunda, alt dosya hızlı sıralama yoluyla yerinde sıralanır ve yazılır. Bu alt dosya şimdi sıralanmıştır ve dosyada yerindedir. Tüm alt dosyalar sıralanıp yerine oturuncaya kadar işleme devam edilir. Dosyadaki ortalama geçiş sayısı yaklaşık 1 + ln(N+1)/(4 B)'dir, ancak en kötü durum modeli N geçiştir (en kötü durum dahili sıralama için O(n^2)'ye eşdeğerdir).

Üç yollu sayı tabanı hızlı sıralama

Bu algoritma, sayı tabanı sıralama ve hızlı sıralamanın bir birleşimidir . Diziden (pivot) bir öğe seçin ve dizenin (multikey) ilk karakterini (anahtarını) göz önünde bulundurun. Kalan öğeleri üç kümeye bölün: karşılık gelen karakterleri pivotun karakterinden küçük, ona eşit ve ondan büyük olanlar. Aynı karakterdeki "küçüktür" ve "büyüktür" bölümlerini yinelemeli olarak sıralayın. "Eşit" bölümünü bir sonraki karaktere (anahtar) göre özyinelemeli olarak sıralayın. Biz tür uzunluğunun bayt veya sözcükleri kullanılarak göz önüne alındığında B bit, en iyi durumda, bir O ( KN ) ve en kötü durumda O (2 K K ) ya da en azından , O ( K 2 ) özgü anahtarlar için verilen standart hızlı sıralama gibi, N- <2 K ve K , hızlı sıralama dahil tüm standart karşılaştırmalı sıralama algoritmalarında gizli bir sabittir . Bu, orta bölümün, pivota tam olarak eşit olan (önemsiz) sıralanmış bir öğe alt dizisini temsil ettiği bir tür üç yönlü hızlı sıralamadır .

Hızlı sayı tabanı sıralama

Ayrıca Powers tarafından O ( K ) paralel PRAM algoritması olarak geliştirilmiştir. Bu yine sayı tabanı sıralama ve hızlı sıralamanın bir birleşimidir ancak hızlı sıralama sol/sağ bölme kararı anahtarın ardışık bitleri üzerinde verilir ve bu nedenle N K -bit anahtarları için O ( KN ) olur . Tüm karşılaştırma sıralama algoritma kabul impliclty transdichotomous modeli ile K olarak İçeride ISTV melerin RWMAIWi'nin (log N ) gibi, K bir nevi olarak daha küçük olan O ( N ) zaman ya da bir karma tablosu kullanılarak sıralama tamsayıdır . Eğer K »günlüğü N ancak unsurlar içinde benzersizdir O (log N ) biti, kalan bitleri ya quicksort veya hızlı sayı tabanı sıralama tarafından baktı edilmeyecektir. Aksi takdirde, tüm karşılaştırmalı sıralama algoritmaları aynı zamanda O ( K ) nispeten yararsız bitlere bakma yüküne sahip olacaktır, ancak hızlı sayı tabanı sıralama , standart hızlı sıralama ve sayı tabanı hızlı sıralamanın en kötü durum O ( N 2 ) davranışlarından kaçınacaktır ve hatta daha hızlı olacaktır. bu benzersizprefix( K ) ≫ log N koşulları altında bu karşılaştırma algoritmalarının en iyi durumunda . Karşılaştırma, sayı tabanı ve paralel sıralamada gizli genel giderler hakkında daha fazla tartışma için Yetkilere bakın.

BlokHızlı Sıralama

Herhangi bir karşılaştırmaya dayalı sıralama algoritmasında, karşılaştırma sayısını en aza indirmek, her karşılaştırmadan elde edilen bilgi miktarını en üst düzeye çıkarmayı gerektirir, bu da karşılaştırma sonuçlarının tahmin edilemez olduğu anlamına gelir. Bu, sık sık şube yanlış tahminlerine neden olarak performansı sınırlar. BlockQuicksort, öngörülemeyen dalları veri bağımlılıklarına dönüştürmek için hızlı sıralama hesaplamalarını yeniden düzenler . Bölümleme sırasında, girdi orta büyüklükteki bloklara bölünür (bunlar veri önbelleğine kolayca sığar ) ve iki dizi, değiştirilecek öğelerin konumlarıyla doldurulur. (Koşullu dallardan kaçınmak için, konum koşulsuz olarak dizinin sonunda saklanır ve bir takas gerekiyorsa sonun dizini artırılır.) İkinci bir geçiş, dizilerde belirtilen konumlardaki öğeleri değiştirir. Her iki döngünün de yalnızca bir koşullu dalı vardır, genellikle alınan bir sonlandırma testi.

Kısmi ve artımlı hızlı sıralama

En küçük veya en büyük k öğelerini girdinin geri kalanından ayıran birkaç hızlı sıralama türü vardır .

genelleme

Richard Cole ve David C. Kandathil, 2004'te, bölüm sıralamaları adı verilen ve ortalama olarak (tüm girdi sıralamaları eşit olasılıkla) çoğu karşılaştırmayı gerçekleştiren (bilgi teorik alt sınırına yakın) ve tek parametreli bir sıralama algoritmaları ailesini keşfettiler. operasyonlar; en kötü ihtimalle karşılaştırmalar (ve ayrıca işlemler) yaparlar; bunlar yerindedir ve yalnızca ek alan gerektirir . Optimize edilmiş hızlı sıralamalara ( Sedgewick ve Bentley - McIlroy'a ) karşı pratik verimlilik ve performansta daha küçük farklılıklar gösterildi .

Ayrıca bakınız

  • Introsort  – Hibrit sıralama algoritması

Notlar

Referanslar

Dış bağlantılar