Get best of the week

Reibungslose Sortierung


Wir tauchen weiterhin in eine Vielzahl von Haufen ein.

Heute analysieren wir eine elegante Bestellmethode, bei der spezielle Haufen basierend auf den Zahlen von Leonardo verwendet werden.

Viele haben von dieser Sortierung gehört, aber nur wenige wissen genau, wie sie funktioniert. Heute werden wir sehen, dass nichts kompliziert ist. Die Methode wurde von der legendĂ€ren Edsger Dijkstra erfunden. Neben den vielen hellsten Errungenschaften in der Theorie der Algorithmen ist er auch der Autor einer solch witzigen Aussage: „Studenten, die zuvor Basic studiert haben, ist es fast unmöglich, gute Programmierung zu unterrichten. Als potenzielle Programmierer haben sie eine irreversible geistige Verschlechterung erfahren. “ Ich hoffe, es ist keine GotteslĂ€sterung, dass die Animation im Artikel mit VBA erstellt wurde :-)







EDISON Software - Webentwicklung
EDISON.

, Android iOS.

! ;-)

Die Heap-Sortierung an sich ist sehr gut, da ihre zeitliche KomplexitÀt unabhÀngig von den Daten O ( n log n ) betrÀgt . Um kein Array darzustellen, verschlechtert sich die KomplexitÀt von Heapsort niemals auf O ( n 2 ) , was beispielsweise bei einer schnellen Sortierung passieren kann. Die Kehrseite der Medaille ist, dass das Sortieren nach einem binÀren Haufen nicht beschleunigt werden kann, O ( n ) -KomplexitÀt auch nicht erwartet werden kann (aber das gleiche schnelle Sortieren kann unter bestimmten Bedingungen solche Indikatoren erreichen).

Im Allgemeinen stand eine Frage auf der Tagesordnung: Ist es möglich, so zu erfinden, dass die zeitliche KomplexitĂ€t des Sortierens nach einem Haufen einerseits nicht geringer ist alsO ( n log n ) , aber in einem gĂŒnstigen Szenario (insbesondere wenn ein fast sortiertes Array verarbeitet wird) auf O ( n ) erhöht ?

Dieses Problem wurde von Edsger Dijkstra persönlich angesprochen, der herausfand, dass dies möglich ist.

Es wird davon ausgegangen, dass diejenigen, die diesen Artikel lesen, verstehen, wie das Sortieren nach Heap im Allgemeinen funktioniert. Sie wissen, was Sortierbaum ist und warum ein Sieben erforderlich ist. Wenn jemand LĂŒcken in diesem Wissen hat, empfehle ich Ihnen, den vorherigen Artikel zu lesen , bevor Sie mit dem Lesen fortfahren .

Was ist los mit einem binÀren Heap?


Lassen Sie uns einen Blick darauf werfen, wie Heapsort ein fast geordnetes Array sortiert und warum dieser Algorithmus solche eingehenden Daten nicht schneller verarbeitet.


Klicken Sie auf die Animation, um zum Artikel „Sortieren nach der n-Pyramide“ zu gelangen.

Das erste, was Ihnen auffĂ€llt, ist, dass beim Sieben die Maxima stĂ€ndig an die Wurzel des Heaps verschoben werden, die dem ersten Element des Arrays entspricht. Wenn das Eingabearray fast geordnet ist, bedeutet dies fĂŒr den Algorithmus nur wenig Arbeit. Kleinere Elemente werden immer noch zuerst den Baum hinuntergehen, d. H. Gehen Sie nĂ€her an das Ende des Arrays heran, nicht an den Anfang.

Der zweite Verlangsamungsfaktor, der nicht so offensichtlich ist, ist, dass der Standard-BinĂ€rheap selbst immer ein ausgeglichener Baum ist. Bei ursprĂŒnglich bestellten Daten spielt dies eine negative Rolle. Wenn das ursprĂŒngliche Array zufĂ€llige Daten enthĂ€lt, werden diese gleichmĂ€ĂŸig in einem ausgeglichenen Baum verteilt, und das mehrfache Sieben durchlĂ€uft alle Zweige ungefĂ€hr gleich oft. Bei fast geordneten Daten ist ein unausgeglichener Baum vorzuziehen. In diesem Fall werden die Daten in dem Teil des Arrays, der lĂ€ngeren Zweigen des Baums entspricht, seltener verarbeitet als in anderen.

Leonardo-Nummern


Um beide Probleme zu lösen, schlug Dijkstra vor, spezielle binÀre Haufen zu verwenden, die auf Leonardo-Zahlen basieren.

Leonardo-Zahlen sind fast wie Fibonacci-Zahlen, aber nur besser.
Eine Reihe von Leonardo-Zahlen wird rekursiv angegeben:

L 0 = 1
L 1 = 1
L n = L n - 1 + L n - 2 + 1

Die ersten 20 Leonardo-Zahlen:
1, 1, 3, 5, 9, 15, 25, 41, 67 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529

Absolut jede ganze Zahl kann als die Summe von Leonardo-Zahlen mit unterschiedlichen Seriennummern dargestellt werden.

Dies ist in unserem Fall sehr nĂŒtzlich. Array von nElemente können nicht immer als ein einzelner Haufen von Leonardo dargestellt werden (wenn n keine Leonardo-Zahl ist). Aber dann kann jedes Array immer in mehrere Subarrays unterteilt werden, die einer unterschiedlichen Anzahl von Leonardo entsprechen, d. H. Haufen unterschiedlicher Ordnung sein.

Hier ist ein Beispiel eines Arrays des 21. Elements, das aus drei Leonard-Haufen besteht. In jedem der Haufen entspricht die Anzahl der Knoten einer beliebigen Anzahl von Leonardo.


Wichtige Punkte zu wissen:

  1. Jeder Leonardov-Stapel ist ein unausgeglichener BinÀrbaum.
  2. Die Wurzel jedes Heaps ist das letzte (und nicht das erste, wie in einem regulÀren binÀren Heap) Element des entsprechenden Subarrays.
  3. Jeder Knoten mit all seinen Nachkommen ist auch ein Leonard-Haufen kleinerer Ordnung.

Haufen bauen und abbauen


In der Wiederholungsformel fĂŒr Leonardo-Zahlen ist

L n = L n - 1 + L n - 2 + 1

sehr zufrieden mit der Einheit am Ende.

Und deshalb. Angenommen, wir haben zwei benachbarte Subarrays im Array, die Heaps entsprechen, die auf zwei benachbarten Leonardo-Zahlen aufgebaut sind. Mit dem Element unmittelbar nach diesen Subarrays können diese Subarrays zu einem gemeinsamen Heap kombiniert werden, der der nÀchsten Leonard-Nummer entspricht.



Wir gehen die Elemente im Array durch und bauen eine Reihe von Leonard-Haufen. Wenn Sie das Element verwenden, können Sie die beiden vorherigen Heaps kombinieren (dies ist nur dann möglich, wenn die beiden vorherigen Heaps zwei aufeinander folgenden Leonardo-Zahlen entsprechen), und dann kombinieren. Wenn eine Kombination nicht möglich ist (die beiden vorherigen Heaps entsprechen nicht zwei aufeinanderfolgenden Leonardo-Nummern), bildet das aktuelle Element einfach einen neuen Heap eines Elements, das der ersten (oder zweiten, wenn die erste zuvor verwendet wird) Leonardo-Nummer entspricht.

In der zweiten Stufe des Algorithmus erfolgt der umgekehrte Prozess - wir analysieren die Haufen. Wenn wir die Wurzel im Heap entfernen, erhalten wir zwei kleinere Heaps, die den beiden vorherigen Leonardo-Zahlen entsprechen. Dies kann geschehen, weil:

L n - 1 = L n - 1+ L n - 2

In Fibonacci-Zahlen gibt es keine solche nĂŒtzliche Einheit, daher verwenden wir den Fibonacci-Heap nicht.

Smooth Sort :: Smoothsort


Der endgĂŒltige Algorithmus:

  • I. Erstellen Sie eine Reihe von Leonard-Haufen aus dem Array, von denen jeder ein Sortierbaum ist.
    • I.1. Durchlaufen Sie die Elemente des Arrays von links nach rechts.
    • II.1. ÜberprĂŒfen Sie, ob das aktuelle Element die beiden am weitesten links liegenden Heaps im vorhandenen Heap von Leonard-Heaps kombinieren kann:
      • II.1.a. Wenn ja, dann kombinieren wir die beiden am weitesten links liegenden Heaps zu einem. Das aktuelle Element wird zur Wurzel dieses Heaps. Wir durchsuchen den kombinierten Heap.
      • II.1.b. Wenn nicht, fĂŒgen Sie das aktuelle Element als neuen Heap (der bisher aus einem Knoten besteht) zum vorhandenen Heap von Leonard-Heaps hinzu.
  • II. , :
    • II.1. . , .
    • II.2. ( ) ( ).
    • II.3. , . .
    • II.4. ( ), .
    • II.5. Nachdem das maximale Element an das Ende verschoben wurde, nahm der sortierte Teil des Arrays zu und der unsortierte Teil ab. Wiederholen Sie die Schritte II.1-II.4 fĂŒr den verbleibenden unsortierten Teil des Arrays.



Beispiel fĂŒr eine Python-Implementierung


import random

def smoothsort(lst):

    #    
    leo_nums = leonardo_numbers(len(lst))


    #       
    heap = []

    #   
    #       
    #       
    for i in range(len(lst)):
        if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
            heap.pop()
            heap[-1] += 1
        else:
            if len(heap) >= 1 and heap[-1] == 1:
                heap.append(0)
            else:
                heap.append(1)
        restore_heap(lst, i, heap, leo_nums)

    #  
    for i in reversed(range(len(lst))):
        if heap[-1] < 2:
            heap.pop()
        else:
            k = heap.pop()
            t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
            heap.append(k_l)
            restore_heap(lst, t_l, heap, leo_nums)
            heap.append(k_r)
            restore_heap(lst, t_r, heap, leo_nums)

#   ,     
def leonardo_numbers(hi):

    a, b = 1, 1
    numbers = []
    while a <= hi:
        numbers.append(a)
        a, b = b, a + b + 1
    return numbers

#        
def restore_heap(lst, i, heap, leo_nums):
    
    #      
    
    current = len(heap) - 1
    k = heap[current]

    while current > 0:
        j = i - leo_nums[k]
        if (lst[j] > lst[i] and
            (k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
            lst[i], lst[j] = lst[j], lst[i]
            i = j
            current -= 1
            k = heap[current]
        else:
            break

    # 
    
    while k >= 2:
        t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
        if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
            if lst[t_r] > lst[t_l]:
                lst[i], lst[t_r] = lst[t_r], lst[i]
                i, k = t_r, k_r
            else:
                lst[i], lst[t_l] = lst[t_l], lst[i]
                i, k = t_l, k_l
        else:
            break

#         ,
#     
def get_child_trees(i, k, leo_nums):

    t_r, k_r = i - 1, k - 2
    t_l, k_l = t_r - leo_nums[k_r], k - 1
    return t_r, k_r, t_l, k_l

#  
def main(n):
    lst = list(range(n))
    random.shuffle(lst)
    print(lst)
    smoothsort(lst)
    print(lst)

Zeitliche KomplexitÀt


Wenn wir ein fast geordnetes Array als Eingabe nehmen, zeigt die Visualisierung, warum ein solches Array viel schneller verarbeitet wird.



Einsparungen entstehen nur durch Sieben. In fast geordneten Daten sinkt das Sieben flach in den Baum, auch nachdem sich die Haufen in der zweiten Stufe allmÀhlich aufgelöst haben. In den anfÀnglich zufÀlligen Daten ist das Sieben teurer, da es oft in seinem Haufen auf die allerletzte Ebene fÀllt.

Lassen Sie uns die GesamtzeitkomplexitÀt schÀtzen.

In der ersten Phase iterieren wir ĂŒber n Elemente und fĂŒgen sie den bereits links vorhandenen Heaps hinzu. Das HinzufĂŒgen zum Heap selbst kostet ungefĂ€hr in O (1), aber fĂŒr den Heap mĂŒssen Sie einen Siebvorgang durchfĂŒhren. In geordneten Daten kostet ein flaches Sieben hĂ€ufig O (1) fĂŒr ein Element, das dem Heap hinzugefĂŒgt wird. Bei ungeordneten Daten wird das Sieben fĂŒr jede Addition in O (log n ) berechnet., da das Sieben aufgrund von ZufĂ€lligkeiten oft bis zum Grund durch die Ebenen des Baumes gehen muss.

Daher ist in der ersten Stufe die beste ZeitkomplexitÀt:
fĂŒr fast geordnete Daten - O ( n ),
fĂŒr zufĂ€llige Daten - O ( n log n ).

FĂŒr die zweite Stufe ist die Situation Ă€hnlich. Wenn Sie das nĂ€chste Maximum austauschen, mĂŒssen Sie den Heap, an dessen Wurzel er sich befand, erneut sieben. Und die Siebmetriken fĂŒr geordnete und ungeordnete Daten sind unterschiedlich.

In der zweiten Stufe ist die beste ZeitkomplexitÀt dieselbe wie in der ersten:
fĂŒr fast geordnete Daten - O ( n ),
fĂŒr zufĂ€llige Daten - O ( n log n ).

HinzufĂŒgen von ZeitkomplexitĂ€t fĂŒr die erste und zweite Stufe:
fĂŒr fast geordnete Daten - O (2 n ) = O ( n ),
fĂŒr zufĂ€llige Daten - O (2 n log n ) = O ( n log n ).

Im Allgemeinen ist die schlechteste und durchschnittliche ZeitkomplexitĂ€t fĂŒr eine reibungslose Sortierung O ( n log n ).
Dijkstra hat in seinen Berechnungen (mit denen ich Sie nicht langweilen werde) bewiesen, dass die beste KomplexitÀt reibungslos zu O ( n ) tendiert, je geordneter die eingehenden Daten sind. Daher der Name - reibungslose Sortierung.

ZusÀtzliche SpeicherkomplexitÀt


Um die Daten in eine Reihe von Leonard-Haufen zu zerlegen, mĂŒssen Sie sich nur genau merken, welche Leonardo-Nummern bei jedem Schritt beteiligt sind. Wenn man diese Zahlen kennt, werden die Haufen selbst algorithmisch ausgerichtet. Diese Zahlenreihe wĂ€chst sehr schnell, sodass Sie selbst fĂŒr große Arrays einen sehr kleinen Satz von Leonard-Zahlen benötigen.

Binomial-Heap-Sortierung :: Binomial-Heap-Sortierung


Es gibt eine Baumstruktur, die der von uns aussortierten sehr Ă€hnlich ist - einen Binomialhaufen . Dies ist auch eine Reihe von Haufen unterschiedlicher GrĂ¶ĂŸe, bei denen die Anzahl der Knoten jeweils eine Zweierpotenz ist. Jedes Array mit einer beliebigen Anzahl von Elementen kann in diesen Heap erweitert werden, da jede natĂŒrliche Anzahl in die Summe von zwei verschiedenen Graden zerlegt wird.

Im Prinzip können Sie eine reibungslose Sortierung basierend auf Binomen durchfĂŒhren:



Wird es schneller funktionieren? Kaum. Der Binomialheap ist nicht binĂ€r, und im letzten Artikel haben wir herausgefunden, dass das Erhöhen der Anzahl der Nachkommen nicht beschleunigt, sondern den Bildschirm verlangsamt . Außerdem können Sie feststellen, dass der Binomialheap lĂ€ngere Verzweigungen aufweist, weshalb benachbarte geordnete Bereiche des Arrays etwas langsamer miteinander verbunden sind.

Es ist nicht bekannt, ob der Dijkstra-Binomialhaufen allgemein als mögliche Grundlage fĂŒr seinen Algorithmus angesehen wurde. Wie dem auch sei, der Leonardov-Haufen ist wahrscheinlich optimaler.

Trailer der nÀchsten Serie


Selbst wenn ein Binomialstapel nicht die beste Option fĂŒr eine reibungslose Sortierung ist, sollten Sie ihn nicht vollstĂ€ndig verwerfen.

Wenn der Binomialbaum leicht modifiziert ist und völlig andere (sehr kĂŒhne) Ideen verwendet werden, um ihn zu umgehen, erhalten wir einen originellen und effektiven Algorithmus, der seine eigenen Vorteile hat. WorĂŒber werden wir das nĂ€chste Mal sprechen?


Klicken Sie auf die Animation, um zum Artikel mit der nÀchsten Sortierung nach Heap zu gelangen.

Verweise


Die glatte / glatte

Leonardo-Zahl , Binomialhaufen / Binomialhaufen

Serienartikel:



Die heutige reibungslose Sortierung wurde der AlgoLab-App hinzugefĂŒgt. Sowie einen Bonus - und das Sortieren mit einem Binomialstapel. Wer also die Daten auf den Heap-Heaps persönlich steuern möchte, aktualisiert die Excel-Datei mit Makros.

More articles:


All Articles