Yığın Sıralaması - Heapsort

yığın sıralaması

Rastgele izin verilen değerler dizisini sıralayan bir yığın sıralaması çalışması. Algoritmanın ilk aşamasında, dizi öğeleri yığın özelliğini karşılayacak şekilde yeniden sıralanır . Gerçek sıralama yapılmadan önce, örnekleme için yığın ağacı yapısı kısaca gösterilir.
Sınıf	sıralama algoritması
Veri yapısı	Dizi
En kötü durum performansı	${\ Displaystyle O(n\log n)}$
En iyi durum performansı	${\ Displaystyle O(n\log n)}$(farklı tuşlar) veya (eşit tuşlar)${\görüntüleme stili O(n)}$
Ortalama performans	${\ Displaystyle O(n\log n)}$
En kötü durum alanı karmaşıklığı	${\görüntüleme stili O(n)}$toplam yardımcı${\görüntüleme stili O(1)}$

Gelen bilgisayar bilimleri , heapsort bir olduğunu karşılaştırma tabanlı sıralama algoritması . Yığın sıralama, gelişmiş bir seçim sıralama olarak düşünülebilir : seçim sıralama gibi, yığın sıralama da girdisini sıralanmış ve sıralanmamış bölgeye ayırır ve ondan en büyük öğeyi çıkarıp sıralanan bölgeye ekleyerek sıralanmamış bölgeyi yinelemeli olarak küçültür. Seçim sıralamadan farklı olarak, yığın sıralama, sıralanmamış bölgenin doğrusal zaman taramasıyla zaman kaybetmez; bunun yerine, yığın sıralama , her adımda en büyük öğeyi daha hızlı bulmak için bir yığın veri yapısında sıralanmamış bölgeyi tutar .

Pratikte çoğu makinede iyi uygulanmış bir hızlı sıralamadan biraz daha yavaş olmasına rağmen , daha uygun bir en kötü durum O( n log n ) çalışma zamanı avantajına sahiptir . Heapsort yerinde bir algoritmadır , ancak kararlı bir sıralama değildir .

Heapsort, 1964'te JWJ Williams tarafından icat edildi . Bu aynı zamanda, Williams tarafından zaten başlı başına yararlı bir veri yapısı olarak sunulan yığının doğuşuydu . Aynı yıl, RW Floyd , bir diziyi yerinde sıralayabilen geliştirilmiş bir sürüm yayınladı ve daha önce treeort algoritması araştırmasına devam etti .

genel bakış

Heapsort algoritması iki bölüme ayrılabilir.

İlk adımda, bir yığın veri (bkz dışına inşa edilmiştir İkili yığın § bir yığın Bina ). Yığın, genellikle tam bir ikili ağaç düzenine sahip bir diziye yerleştirilir . Tam ikili ağaç, ikili ağaç yapısını dizi indekslerine eşler; her dizi dizini bir düğümü temsil eder; düğümün ebeveyninin, sol alt dalının veya sağ alt dalının dizini basit ifadelerdir. Sıfır tabanlı bir dizi için kök düğüm 0 dizininde depolanır; eğer io anda geçerli düğümün endeksi ise

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer.
  iLeftChild(i)  = 2*i + 1
  iRightChild(i) = 2*i + 2

İkinci adımda, en büyük öğe yığından (yığın kökü) art arda çıkarılarak ve diziye eklenerek sıralı bir dizi oluşturulur. Yığın özelliğini korumak için yığın, her kaldırma işleminden sonra güncellenir. Tüm nesneler öbekten kaldırıldığında, sonuç sıralanmış bir dizidir.

Heapsort yerinde gerçekleştirilebilir. Dizi, sıralı dizi ve yığın olmak üzere iki bölüme ayrılabilir. Yığınların diziler olarak depolanması burada şemalandırılmıştır . Yığının değişmezi her çıkarmadan sonra korunur, bu nedenle tek maliyet çıkarmanın maliyetidir.

algoritma

Heapsort algoritması, listeyi önce maksimum yığına dönüştürerek hazırlamayı içerir . Algoritma daha sonra tekrar tekrar listenin ilk değerini son değerle değiştirir, yığın işleminde dikkate alınan değer aralığını bir azaltır ve yeni ilk değeri yığındaki konumuna eler. Bu, dikkate alınan değerler aralığı uzunluk olarak bir değer olana kadar tekrarlanır.

Adımlar:

1. Listedeki buildMaxHeap() işlevini çağırın. Heapify() olarak da anılır, bu, O(n) işlemlerinde bir listeden bir yığın oluşturur.
2. Listenin ilk öğesini son öğeyle değiştirin. Listenin dikkate alınan aralığını birer birer azaltın.
3. Yığındaki uygun dizinine yeni ilk öğeyi elemek için listedeki siftDown() işlevini çağırın.
4. Listenin dikkate alınan aralığı tek bir öğe değilse adım (2)'ye gidin.

buildMaxHeap() işlemi bir kez çalıştırılır ve performansta O( n ) olur. SiftDown () fonksiyonu O (log n ) ve adı n defa. Bu nedenle, bu algoritmanın performansı O( n + n log n ) = O( n log n ) şeklindedir .

sözde kod

Algoritmayı pseudocode'da uygulamanın basit bir yolu aşağıdadır . Diziler sıfır tabanlıdır ve swapdizinin iki öğesini değiştirmek için kullanılır. 'Aşağı' hareket, kökten yapraklara veya alt endekslerden daha yükseğe doğru anlamına gelir. Sıralama sırasında en büyük öğenin yığının kökünde a[0], sıralamanın sonunda ise en büyük öğenin içinde olduğuna dikkat edin a[end].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

Sıralama yordamı iki alt yordam kullanır heapifyve siftDown. İlki, yerinde yığın oluşturma rutini iken ikincisi, uygulamak için ortak bir alt rutindir heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            swap(a[root], a[swap])
            root ← swap            (repeat to continue sifting down the child now)

heapifyİşlem arda kurma aşağı eleme ile aşağıdan yukarıya doğru bir yığın yapı olarak düşünülebilir yığın özelliği . Yığını yukarıdan aşağıya oluşturan ve yukarı doğru eleyen alternatif bir versiyonun (aşağıda gösterilmiştir) anlaşılması daha kolay olabilir. Bu siftUpsürüm, boş bir yığınla başlayıp art arda öğeler ekleyen olarak görselleştirilebilir, oysa siftDownyukarıda verilen sürüm, tüm girdi dizisini dolu ancak "bozuk" bir yığın olarak ele alır ve önemsiz olmayan son alt yığından başlayarak "onarır" ( yani, son üst düğüm).

"SiftDown" sürümü ile "siftUp" sürümü arasındaki zaman karmaşıklığı farkı.

Ayrıca, siftDownheapify sürümü vardır O ( n ) zaman karmaşıklığı ise, siftUpaşağıda verilen sürümü, O ( n log n ) bağlı bir boş yığın her öğe, her seferinde bir tane ekleme ile denklik için zaman karmaşıklığı. Bu, bir bakışta mantıksız görünebilir, çünkü ilkinin logaritmik zaman eleme işlevine ikincisinin yalnızca yarısı kadar çağrı yaptığı açıktır; yani, asimptotik analizi hiçbir zaman etkilemeyen sabit bir faktörle farklılık gösteriyor gibi görünüyorlar.

Karmaşıklıktaki bu farklılığın arkasındaki sezgiyi kavramak için, herhangi bir eleme çağrısı sırasında meydana gelebilecek takas sayısının, çağrının yapıldığı düğümün derinliği ile arttığına dikkat edin. İşin püf noktası, bir yığındaki "sığ" düğümlerden çok (katlanarak çok sayıda) daha "derin" düğümler olmasıdır, böylece siftUp'ın tam logaritmik çalışma süresi, düğümlerde yapılan yaklaşık doğrusal çağrı sayısı üzerinde olabilir. veya yığının "altına" yakın. Öte yandan, herhangi bir eleme çağrısı sırasında oluşabilecek takas sayısı, çağrının yapıldığı düğümün derinliği arttıkça azalır . Bu nedenle, en altta ve en çok sayıda düğüm katmanında siftDown heapifybaşladığında ve çağırdığında siftDown, her eleme çağrısı, en fazla, üzerinde bulunduğu düğümün "yüksekliğine" (yığının altından) eşit sayıda değiş tokuşa neden olacaktır. eleme çağrısı yapılır. Başka bir deyişle, elekDown çağrılarının yaklaşık yarısında en fazla yalnızca bir takas olur, ardından çağrıların yaklaşık dörtte biri en fazla iki takas vb. olacaktır.

Heapsort algoritmasının kendisi, heapify'ın her iki sürümünü kullanarak O ( n log n ) zaman karmaşıklığına sahiptir.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

siftDownHer değiş tokuştan sonra siftDown, bozuk yığını onarmak için yalnızca alt yordamı çağırmanız gereken yaklaşımın aksine ; siftUpyalnız altprogram kırık yığın düzeltemez. Yığın, bir heapifytakastan sonra her seferinde prosedürü çağırarak oluşturulmalıdır, çünkü "siftUp", değiştirilen öğenin son yerinde sona erdiğini varsayar, "siftDown" yerine, öbekte daha düşük öğelerin sürekli ayarlanmasına izin verir. değişmez memnun. siftUpYaklaşımı kullanmak için ayarlanmış sözde kod aşağıda verilmiştir.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Varyasyonlar

Floyd'un yığın inşaatı

Tüm pratik uygulamalarda yer alan temel algoritmanın en önemli varyasyonu, Floyd'un O ( n ) zamanında çalışan ve siftup yerine siftdown kullanan ve siftup uygulama ihtiyacını ortadan kaldıran bir yığın oluşturma algoritmasıdır .

Önemsiz bir yığınla başlayıp tekrar tekrar yaprak eklemek yerine, Floyd'un algoritması yapraklarla başlar, bunların önemsiz ancak kendi başlarına geçerli yığınlar olduklarını gözlemler ve ardından üst öğeleri ekler. n /2 öğesiyle başlayıp geriye doğru giderek, her bir dahili düğüm, eleme yoluyla geçerli bir yığının kökü haline getirilir. Son adım, ilk öğeyi elemek, ardından tüm dizi yığın özelliğine uyar.

Floyd'un Heapsort'un yığın oluşturma aşaması sırasındaki en kötü karşılaştırma sayısının 2 n − 2 s ₂ ( n ) − e ₂ ( n ) 'ye eşit olduğu bilinmektedir , burada s ₂ ( n ) 1 bitin sayısıdır n ve e'nin ikili gösteriminde ₂ ( n ) izleyen 0 bit sayısıdır.

Floyd'un yığın oluşturma algoritmasının standart uygulaması , veri boyutu CPU önbelleğini aştığında çok sayıda önbellek kaçırmaya neden olur . Büyük veri kümelerinde çok daha iyi performans, yukarıdakine geçmeden önce tüm alt yığınları tek bir düzeyde birleştirmek yerine, alt yığınları mümkün olan en kısa sürede birleştirerek derinlemesine birinci sırada birleştirerek elde edilebilir.

Aşağıdan yukarıya yığın sıralaması

Aşağıdan yukarıya yığın sıralaması, önemli bir faktörün gerektirdiği karşılaştırma sayısını azaltan bir değişkendir. Sıradan yığın sıralaması, en kötü durum ve ortalamada 2 n log ₂ n + O ( n ) karşılaştırmaları gerektirirken, aşağıdan yukarıya değişken, ortalama olarak n log ₂ n + O (1) ve 1,5 n log ₂ n + O ( n ) en kötü durumda.

Karşılaştırmalar ucuzsa (örneğin tamsayı anahtarları), yukarıdan aşağıya yığınlar zaten bellekten yüklenmiş değerleri karşılaştırdığı için fark önemsizdir. Bununla birlikte, karşılaştırmalar bir işlev çağrısı veya başka bir karmaşık mantık gerektiriyorsa, aşağıdan yukarıya yığın sıralaması avantajlıdır.

Bu, siftDownprosedürün iyileştirilmesiyle gerçekleştirilir . Değişiklik, doğrusal zamanlı yığın oluşturma aşamasını biraz iyileştirir, ancak ikinci aşamada daha önemlidir. Sıradan yığın sıralaması gibi, ikinci aşamanın her yinelemesi yığının tepesini, a [0] çıkarır ve bıraktığı boşluğu bir [ end ] ile doldurur , ardından bu son öğeyi yığından aşağıya doğru eler. Ancak bu öğe yığının en alt seviyesinden gelir, yani yığındaki en küçük öğelerden biridir, bu nedenle aşağı eleme muhtemelen onu geri taşımak için birçok adım alacaktır. Sıradan bir yığın sıralamasında, elemenin her adımı, en az üç öğeyi bulmak için iki karşılaştırma gerektirir: yeni düğüm ve iki çocuğu.

Aşağıdan yukarıya yığın sıralaması bunun yerine, düzey başına yalnızca bir karşılaştırma kullanarak en büyük çocukların ağacın yaprak düzeyine giden yolunu bulur (sanki −∞ ekliyormuş gibi). Başka bir deyişle, kendisinin ve tüm atalarının kardeşlerinden büyük veya eşit olma özelliğine sahip bir yaprak bulur. (Eşit anahtarların yokluğunda, bu yaprak benzersizdir.) Ardından, bu yapraktan yukarı doğru (düzey başına bir karşılaştırma kullanarak) bir [ bitiş ] eklemek için bu yoldaki doğru konumu arar . Bu, sıradan yığın sınıflandırması bulgularıyla aynı konumdur ve eklemeyi gerçekleştirmek için aynı sayıda değişim gerektirir, ancak bu konumu bulmak için daha az karşılaştırma gerekir.

En dibe kadar gittiği ve sonra geri geldiği için bazı yazarlar tarafından sıçramalı yığın olarak adlandırılır .

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

'nin dönüş değeri leafSearch, değiştirilmiş siftDownrutinde kullanılır:

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

Aşağıdan yukarıya yığın sıralaması, ≥16000 boyutundaki dizilerde hızlı sıralama (ortalama üç pivot seçimiyle) olarak açıklandı.

Bu algoritmanın 2008'de yeniden değerlendirilmesi, tamsayı anahtarları için sıradan yığın sıralamasından daha hızlı olmadığını gösterdi, çünkü muhtemelen modern dal tahmini , aşağıdan yukarıya yığının kaçınmayı başardığı öngörülebilir karşılaştırmaların maliyetini geçersiz kılıyor.

Daha ileri bir iyileştirme, seçilen yaprağa giden yolda ikili arama yapar ve en kötü durumda ( n +1)(log ₂ ( n +1) + log ₂ log ₂ ( n +1) + 1.82) + O sıralar (log ₂ , n ) yaklaşırken, karşılaştırma bilgileri-teorik alt sınırı oluşturan bir n log ₂ n - 1,4427 n karşılaştırmaları.

İç düğüm başına iki ekstra bit kullanan bir varyant ( n -1 bit bir için toplam n daha az kullanır: çocuk daha büyük (sol, sağ ve bilinmeyen iki bit üç vaka saklamak için gereklidir) olduğu hakkında önbellek bilgilere -eleman yığın) daha n- log ₂ , n + 1.1 n karşılaştırır.

Diğer varyasyonlar

• Üçlü yığın sıralaması , ikili bir yığın yerine üçlü bir yığın kullanır ; yani, yığındaki her öğenin üç çocuğu vardır. Programlaması daha karmaşıktır, ancak sabit sayıda daha az takas ve karşılaştırma işlemi yapar. Bunun nedeni, üçlü bir yığındaki her bir gözden geçirme adımının üç karşılaştırma ve bir takas gerektirmesine karşın, ikili bir yığında iki karşılaştırma ve bir takasın gerekli olmasıdır. Üçlü bir yığındaki iki düzey 3 ² = 9 öğeyi kapsar, ikili yığında yalnızca 2 ³ = 8'i kapsayan üç düzeyle aynı sayıda karşılaştırmayla daha fazla iş yapar. , çünkü ek karmaşıklık küçük tasarruflara değmez ve aşağıdan yukarıya yığın sıralaması her ikisini de yener.
• Bellek açısından optimize edilmiş yığın sıralaması, çocuk sayısını daha da artırarak yığının referans yerini iyileştirir . Bu, karşılaştırma sayısını artırır, ancak tüm alt öğeler bellekte ardışık olarak depolandığından, yığın geçişi sırasında erişilen önbellek satırlarının sayısını azaltır , bu da net bir performans artışıdır.
• Yer dışı yığın sıralaması, en kötü durumu ortadan kaldırarak aşağıdan yukarıya yığın sıralamasını iyileştirir ve n log ₂ n + O ( n ) karşılaştırmalarını garanti eder . Maksimum değer alındığında, boşalan alanı sıralanmamış bir veri değeriyle doldurmak yerine , asla geri "sekmeyen" bir −∞ sentinel değeriyle doldurun . Bunun yerinde (ve özyinelemeli olmayan) bir "QuickHeapsort" algoritmasında ilkel olarak kullanılabileceği ortaya çıktı. İlk olarak, hızlı sıralama benzeri bir bölümleme geçişi gerçekleştirirsiniz, ancak dizideki bölümlenmiş verilerin sırasını tersine çevirirsiniz. Diyelim ki ( genelliği kaybetmeden ), daha küçük bölümün, dizinin sonuna gitmesi gereken pivottan daha büyük olduğunu, ancak ters bölümleme adımımızın onu başlangıca yerleştirdiğini varsayalım . Daha küçük bölümden bir yığın oluşturun ve çıkarılan maksimumları dizinin sonundaki değerlerle değiştirerek bunun üzerinde yerinde olmayan yığın sıralaması yapın. Bunlar pivottan küçüktür, yani yığındaki herhangi bir değerden küçüktür, bu nedenle −∞ sentinel değerler olarak hizmet eder . Yığın sıralaması tamamlandıktan sonra (ve pivot, dizinin şimdi sıralanan ucundan hemen öncesine taşındı), bölümlerin sırası tersine çevrilir ve dizinin başlangıcındaki daha büyük bölüm aynı şekilde sıralanabilir. ( Kuyruksuz özyineleme olmadığından , bu aynı zamanda hızlı sıralamanın O (log n ) yığın kullanımını da ortadan kaldırır .)
• Rahat sıralama algoritması tarafından geliştirilen HizliSiralama bir varyasyonu Edsger Dijkstra'nın HizliSiralama gibi 1981 yılında, üst kaçınılmazdır rahat sıralama olduğunu Ç ( n log n ) . Düzgün sıralamanın avantajı , girdi zaten bir dereceye kadar sıralanmışsa, O ( n ) zamanına yaklaşırken, yığın sıralamanın ortalamaları , ilk sıralama durumundan bağımsız olarak O ( n log n ) olur . Karmaşıklığı nedeniyle, smoothsort nadiren kullanılır.
• Levcopoulos ve Petersson, bir Kartezyen ağaç yığınına dayanan bir yığın çeşidini tanımlar . İlk olarak, girişten O ( n ) zamanında bir Kartezyen ağaç oluşturulur ve kökü 1 elemanlı ikili yığına yerleştirilir. Ardından ikili yığından tekrar tekrar minimumu çıkarırız, ağacın kök öğesini çıkarırız ve kendileri Kartezyen ağaçları olan sol ve sağ çocuklarını (varsa) ikili yığına ekleriz. Gösterdikleri gibi, eğer girdi zaten neredeyse sıralanmışsa, Kartezyen ağaçlar çok dengesiz olacak, birkaç düğümün sol ve sağ çocukları olacak, bu da ikili yığının küçük kalmasına ve algoritmanın O'dan daha hızlı sıralama yapmasına izin verecek ( n log n ) zaten neredeyse sıralanmış girdiler için.
• Zayıf yığın sıralaması gibi çeşitli değişkenler , düğüm başına fazladan bir bit durum kullanarak, en kötü durumda teorik minimuma yakın n log ₂ n + O (1) karşılaştırmaları gerektirir . Bu ekstra bit, algoritmaları gerçekten yerinde yapmazken, öğenin içinde bunun için yer bulunabilirse, bu algoritmalar basit ve verimlidir, ancak anahtar karşılaştırmaları yeterince ucuzsa (örneğin tamsayı anahtarları) ikili yığınlardan daha yavaştır. sabit faktör önemli değil.
• Katajainen'in "nihai yığın sıralaması" ekstra depolama gerektirmez, n log ₂ n + O (1) karşılaştırması ve benzer sayıda öğe hareketi gerçekleştirir. Bununla birlikte, karşılaştırmalar çok pahalı olmadıkça daha da karmaşıktır ve haklı değildir.

Diğer türlerle karşılaştırma

Heapsort öncelikle , başka bir çok verimli genel amaçlı yerinde karşılaştırma tabanlı sıralama algoritması olan quicksort ile rekabet eder .

Heapsort'un başlıca avantajları, basit, özyinelemeli olmayan kodu, minimum yardımcı depolama gereksinimi ve güvenilir bir şekilde iyi performansıdır: en iyi ve en kötü durumları, birbirinin küçük bir sabit faktörü ve karşılaştırma türlerindeki teorik alt sınır dahilindedir . Önceden sıralanmış girdiler için O ( n log n ) ' den daha iyisini yapamasa da, hızlı sıralamanın O ( n ² ) en kötü durumundan da etkilenmez . (İkincisi dikkatli uygulanması ile önlenebilir, ama bu markaları quicksort çok daha karmaşık ve en popüler çözümlerden biri, içgözlemle sıralama , kullanımları amaçla Heapsort.)

Başlıca dezavantajları, zayıf referans yeri ve doğası gereği seri doğasıdır; örtük ağaca erişimler geniş çapta dağınık ve çoğunlukla rastgeledir ve onu paralel bir algoritmaya dönüştürmenin basit bir yolu yoktur .

Bu onu gömülü sistemlerde , gerçek zamanlı bilgi işlemde ve Linux çekirdeği gibi kötü niyetli olarak seçilen girdilerle ilgili sistemlerde popüler hale getirir . Ayrıca, sıralamada darboğaz olmasını beklemeyen herhangi bir uygulama için iyi bir seçimdir .

İyi uygulanmış bir hızlı sıralama, yığın sıralamadan genellikle 2-3 kat daha hızlıdır. Hızlı sıralama daha az karşılaştırma gerektirse de, bu küçük bir faktördür. (İki kat daha fazla karşılaştırma olduğunu iddia eden sonuçlar, yukarıdan aşağıya sürümü ölçüyor; bkz. § Aşağıdan yukarıya yığın sıralaması .) Hızlı sıralamanın ana avantajı, çok daha iyi referans konumudur : bölümleme, iyi bir uzamsal konuma sahip doğrusal bir taramadır ve özyinelemeli alt bölümlemedir. iyi bir zamansal lokaliteye sahiptir. Ek çaba ile, çabuk da çoğunlukla uygulanabilir dal içermeyen kod ve birden çok CPU paralel olarak alt bölümler sıralamak için kullanılabilir. Bu nedenle, ek performans uygulama çabasını haklı çıkardığında hızlı sıralama tercih edilir.

Diğer büyük O ( n log n ) sıralama algoritması birleştirme sıralamadır , ancak bu, yerinde olmadığı için nadiren doğrudan yığın sıralama ile rekabet eder. Birleştirme sıralamanın Ω( n ) fazladan boşluk (giriş boyutunun kabaca yarısı kadar ) gereksinimi, birleştirme sıralamanın açık bir avantajı olduğu durumlar dışında genellikle engelleyicidir:

• Bir zaman istikrarlı sıralama gereklidir
• (Kısmen) önceden sıralanmış girdiden yararlanırken
• Bağlantılı listeleri sıralama (bu durumda birleştirme sıralama minimum fazladan alan gerektirir)
• Paralel sıralama; birleştirme sıralama, hızlı sıralamadan bile daha iyi paralelleşir ve doğrusal hıza yakın bir hıza kolayca ulaşabilir
• Dış sıralama ; birleştirme sıralaması mükemmel bir referans konumuna sahiptir

Örnek

Küçükten büyüğe sıralamak istediğimiz liste { 6, 5, 3, 1, 8, 7, 2, 4 } olsun. ('Yığın Oluşturma' adımı için NOT: Daha büyük düğümler, daha küçük düğüm üst öğelerinin altında kalmazlar. Üst düğümlerle değiştirilirler ve daha sonra, yığın ikili ağacında daha büyük sayıları küçük sayıların üzerinde tutmak için başka bir değiş tokuşun gerekli olup olmadığı tekrar tekrar kontrol edilir. .)

Heapsort'a bir örnek.

Notlar

Referanslar

• Williams, JWJ (1964), "Algorithm 232 - Heapsort", Communications of the ACM , 7 (6): 347–348, doi : 10.1145/512274.512284
• Floyd, Robert W. (1964), "Algorithm 245 - Treesort 3", Communications of the ACM , 7 (12): 701, doi : 10.1145/355588.365103 , S2CID  52864987
• Carlsson, Svante (1987), "Yığın sıralamasında ortalama durum sonuçları", BIT , 27 (1): 2–17, doi : 10.1007/bf01937350 , S2CID  31450060
• Knuth, Donald (1997), "§5.2.3, Seçime Göre Sıralama", Sıralama ve Arama , Bilgisayar Programlama Sanatı , 3 (üçüncü baskı), Addison-Wesley, s. 144–155, ISBN 978-0-201-89685-5
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein . Algoritmalara Giriş , İkinci Baskı. MIT Press ve McGraw-Hill, 2001. ISBN  0-262-03293-7 . 6. ve 7. Bölümler Sırasıyla: Yığın Sıralaması ve Öncelik Kuyrukları
• Dijkstra'nın Smoothsort'taki orijinal makalesinin bir PDF'si
• Yığınlar ve Yığınlar Eğitimi David Carlson, St. Vincent Koleji

Dış bağlantılar

• Hareketli Sıralama Algoritmaları: Öbek Sıralama de Wayback Machine (2015 6 Mart arşivlenmiş) - grafiksel gösteri
• Univ'den Heapsort ile ilgili eğitim yazılımı. Oldenburg - Metin, animasyonlar ve etkileşimli alıştırmalarla
• NIST'in Algoritmalar ve Veri Yapıları Sözlüğü: Heapsort
• 12 dilde uygulanan Heapsort
• Sıralama , Paul Hsieh tarafından yeniden ziyaret edildi
• Eğitimciler için Yığın sıralamanın nasıl çalıştığını gösteren bir PowerPoint sunumu .
• Açık Veri Yapıları - Bölüm 11.1.3 - Yığın Sıralama , Pat Morin