Bitweise schnelle Drei-Wege-Sortierung

    Hallo allerseits! Heute werden wir über den weniger bekannten Sortieralgorithmus sprechen - das bitweise schnelle Drei-Wege-Sortieren. Dieser Algorithmus ist eine Mischung aus der bekannten schnellen Sortierung und der bitweisen Sortierung.

    Details - unter dem Schnitt.

    Aber für den Anfang erinnern Sie sich an die alten.

    Schnelle Sortierung (QSort)


    Die meisten kennen sie. Kurz gesagt - wir nehmen das unterstützende Element, indem wir es austauschen, so dass kleinere Elemente auf der einen Seite des Arrays und größere oder gleiche auf der anderen Seite verbleiben. Als Nächstes führen wir dieselbe Prozedur rekursiv für die resultierenden Teile aus. Das tragende Element selbst befand sich bereits an der Stelle, an der es sich im sortierten Array befinden wird.

    Gleichzeitig sprechen sie oft von schnellen Sortieroptimierungen. Die bekannteste Optimierung ist die zufällige Auswahl eines Stützelements. Daher ist die Wahrscheinlichkeit eines "Treffers" in dem Fall, in dem eine schnelle Sortierung die schlechteste Leistung zeigt (O (n 2), wie wir uns alle erinnern), signifikant verringert.

    Die zweithäufigste Idee ist, das Array in drei Teile zu unterteilen, nicht in zwei. Elemente sind kleiner als die Referenz, gleich und Elemente sind größer als die Referenz. Diese Optimierung beschleunigt die Ausführungszeit in Fällen, in denen viele identische Elemente im ursprünglichen Array vorhanden sind - schließlich sind sowohl die Referenzelemente als auch die bereits vorhandenen Referenzelemente an ihre Position im sortierten Array "gefallen", und es sind keine zusätzlichen Verfahren zum Sortieren erforderlich. Sowohl die Anzahl der ausgeführten Operationen als auch die Tiefe der rekursiven Aufrufe werden reduziert. Im Allgemeinen ein guter Weg, um ein wenig zu sparen.

    Komplexität - O (n log n) im Durchschnitt O (n ^ 2) am schlechtesten, dop.pamyat - O (log n)

    Wenn das hier gut und prägnant geschrieben.

    Bitweises Sortieren (Radix-Sortieren)


    Ein etwas weniger populärer Algorithmus, aber bekannt genug. Die Logik seiner Arbeit ist einfach. Nehmen wir an, wir haben eine Reihe von Zahlen.

    Zuerst sortieren wir sie nach dem ersten (höchsten) Rang. Die Sortierung erfolgt dann über die Zählsortierung. Schwierigkeit ist o (n). Wir haben 10 „Körbe“ - in denen die Oberstufe 0, 1, 2 usw. ist. Als nächstes beginnen wir in jedem der Körbe das gleiche Verfahren, aber wir betrachten nur nicht die höhere Ebene, sondern die nächste usw.

    Es gibt so viele Schritte wie Ziffern in Zahlen. Dementsprechend ist die Komplexität des Algorithmus O (n · k), k ist die Anzahl der Bits.

    Es gibt zwei Arten einer solchen Sortierung - MSD (höchstwertige Ziffer - erstes höherwertiges Bit) und LSD (niedrigstwertige Ziffer - erstes niederwertiges Bit). Zum Sortieren von Zahlen ist LSD etwas bequemer, weil Es ist nicht erforderlich, den Zahlen auf der linken Seite eine unbedeutende 0 zuzuweisen, um die Anzahl der Ziffern auszugleichen.
    MSD ist bequemer zum Sortieren von Zeichenfolgen.

    Der Algorithmus in dieser Implementierung erfordert zusätzlichen Speicher - O (n).

    Lesen Sie mehr kann zum Beispiel hier .

    Bitweises Sortieren in drei Richtungen


    Angenommen, wir sortieren Zeichenfolgen.

    Die Verwendung von qsort, mit dem Elemente aktiv verglichen werden, ist zu teuer - ein Zeichenfolgenvergleich ist eine lange Operation. Ja, wir können unseren eigenen Komparator schreiben, der etwas effizienter sein wird. Aber trotzdem.

    Die Verwendung von radix, das zusätzlichen Speicher benötigt, ist ebenfalls nicht sehr motivierend - die Zeilen können groß sein. Ja, und eine große Anzahl von Zeilen, d.h. Die Anzahl der Entladungen drückt auf den Wirkungsgrad.

    Aber was ist, wenn Sie diese Algorithmen auf irgendeine Weise kombinieren?

    Die Logik des resultierenden Algorithmus ist wie folgt:

    1. Wir nehmen das Unterstützungselement.
    2. Wir teilen das Array in drei Teile auf und vergleichen die Elemente mit der Referenz in der Kategorie Senior - in kleinere, gleiche und große.
    3.In jedem der drei Teile wiederholen wir den Vorgang, beginnend mit Schritt Nr. 1, bis wir die leeren Teile oder Teile mit 1 Element erreichen.

    Nur im mittleren Teil (das heißt, wo das ältere Bit gleich dem höchsten Bit des tragenden Elements ist) gehen wir zum nächsten Bit über. In den übrigen Teilen beginnt der Betrieb ohne Änderung der "Arbeits" -Entladung.

    Die Komplexität der Sortierung ist O (nlogn). Zusätzlicher Speicher ist O (1).

    Der Nachteil dieses Algorithmus ist, dass er im Gegensatz zur bitweisen Sortierung das Array in nur drei Teile aufteilt, was beispielsweise die Möglichkeiten einer Multithread-Implementierung einschränkt. Der Vorteil gegenüber dem schnellen Sortieren besteht darin, dass nicht alle Elemente verglichen werden müssen. Der Vorteil gegenüber der bitweisen Sortierung ist, dass wir keinen zusätzlichen Speicher benötigen.

    Unabhängig davon ist anzumerken, dass eine solche Sortierung bequem zu verwenden ist, wenn das Element des ursprünglichen Arrays ein anderes Array ist. Wenn dann das anfängliche Array eingegeben wird, wird beispielsweise die höchste Ordnung eingegeben [i] [0], die nächste wird eingegeben [i] [1] usw. Diese Sortierung wird als mehrdimensionaler QuickSort oder mehrtägiger QuickSort bezeichnet.

    Immer detaillierter - R. Sedgwick, Grundlegende Algorithmen in C ++, Teil 3, Kap. 10, 10.4 „Bitweise schnelle Drei-Wege-Sortierung“

    Das Schema des Algorithmus:

    Bild

    Nochmals zur Dreiteilung


    Beachten Sie, dass die Aufteilung des Arrays in drei Teile der relativen Referenz am einfachsten mit dem Bentley- und McIlroy-Algorithmus implementiert werden kann. Es besteht darin, dass der folgende Zusatz (unmittelbar nach dem Austausch von Elementen) in das Standardverfahren zur Trennung von qsort eingeführt wird.

    Wenn das verarbeitete Element in den linken Teil des Arrays fällt (d. H. Nicht größer als die Referenz ist) und mit der Referenz übereinstimmt, wird es durch Austausch mit dem entsprechenden Element (das bereits vollständig verarbeitet wurde und dementsprechend kleiner als die Referenz ist) auf der linken Seite des Arrays platziert. Befindet sich das verarbeitete Element auf der rechten Seite des Arrays und entspricht es der Referenz, wird es auf der rechten Seite des Arrays platziert.

    Nach Abschluss des Trennvorgangs ist bereits genau bekannt, dass gleiche Elemente in die Mitte des Arrays übertragen werden (unmittelbar nach Elementen, die kleiner als das Referenzelement sind), wenn die Anzahl der Elemente kleiner als das Referenzelement ist.

    Details dazu finden Sie in R. Sedgwick - Grundlegende Algorithmen in C ++, Teil 3, Kap. 7, Abschnitt 7.6, „Doppelte Schlüssel“.

    Jetzt auch beliebt: