Amerikanische Flagge sortieren

Um das Funktionsprinzip dieser "Multiband" -Sortierung zu verstehen, ist es einfacher, mit einem Beispiel einer Flagge mit drei Streifen zu beginnen. Und um die Dreifarben-Flagge leichter handhaben zu können, ist es besser, zuerst zu sehen, wie sie mit dem Zweifarben-Beispiel funktioniert. Und mit zwei Farben umgehen ...

Dieser Artikel wurde mit der Unterstützung von EDISON verfasst.

Wir befassen uns mit der Portierung und Migration von Software sowie der Entwicklung mobiler Anwendungen für Android und iOS .

Wir lieben die Theorie der Algorithmen! ;-)

Zweifarbige Flagge

Betrachten Sie zunächst den Fall, in dem die Zahlen im sortierten Array in nur zwei Bits verteilt sind. Der Einfachheit halber nehmen wir an, dass wir ein Array von Nullen (niedriger Ordnung) und Einsen (hoher Ordnung) haben.

Wir haben also nur zwei "Bänder": In einem werden wir die niedrigstwertigen Bits (Nullen) und in dem anderen die höchsten Bits (Einheiten) verschieben. Jede zweifarbige Flagge dient zur Demonstration. Zum Beispiel die Flagge der Ukraine.



Was ist hier los? Da in der ersten Phase nicht bekannt ist, wie viele Nullen und wie viele Einheiten wir haben, ist unklar, in welcher Größe die einzelnen „Bänder“ enden werden. Daher setzen wir zwei Zeiger auf die Tasten des Arrays. Bei niedriger Ordnung wird der Zeiger an den Anfang des Arrays gesetzt, bei hoher Ordnung an das Ende. Dann durchlaufen wir das Array einmal von links nach rechts und betrachten jedes Bitelement.

Wenn während der Passage ein Element der höchsten Ordnung entspricht, teilt uns der zweite Zeiger mit, wohin dieses Element übertragen werden soll (wir führen einen Austausch durch). Der Zeiger zum Einfügen des nächsten Elements bewegt sich nach links, der "Streifen" für die übergeordnete Ziffer hat sich erweitert.

Wenn es gleich der niedrigstwertigen Ziffer ist, bewegen wir den Zeiger dafür um ein Element nach rechts. Da wir nur zwei Ziffern haben, muss das Element nicht übertragen werden, es ist bereits an seiner Stelle. Der „Streifen“ für die jüngere Kategorie wurde natürlich breiter.

Infolgedessen kollidieren zwei aufeinander zu bewegende Zeiger an einem Punkt, und die Entladungen werden in ihren "Bändern" angeordnet. Gleichzeitig müssen Sie nicht das gesamte Array durchlaufen - wenn sich die Zeiger irgendwo in der Mitte treffen, erledigt der Algorithmus seine Aufgabe.

Das Problem der niederländischen Nationalflagge :: Das Problem der niederländischen Nationalflagge

Wir erschweren die Aufgabe ein wenig und berücksichtigen nicht zwei, sondern drei Ziffern. Lassen Sie uns die Elemente des Arrays zu den niedrigsten (Nullen), mittleren (Einheiten) und höheren (zwei) Ziffern gehören.

Zur Demonstration nehmen wir die dreifache rot-weiß-blaue Flagge von Frankreich, Luxemburg von Russland und Schleswig-Goldstein von den Niederlanden. Warum genau die Flagge der Niederlande? Denn Edsger Dijkstra hat in seinen Vorlesungen am Beispiel dieser Flagge den entsprechenden Algorithmus untersucht, der als "Aufgabe der niederländischen Nationalflagge" bezeichnet wurde.



Wie Sie sehen, gibt es nichts besonders Neues. Jede Kategorie hat einen eigenen Zeiger. Anfangs nehmen die Beschriftungen für Junior und Middle die Startpositionen am Anfang des Arrays ein und bewegen sich nach rechts, wenn das entsprechende Element angetroffen wird. Der Zeiger für die höhere Ordnung befindet sich zuerst am Ende des Arrays und bewegt sich nach links.

Das Durchlaufen des Arrays ist auch in der Tat unvollständig. Wenn die Bits mehr oder weniger gleichmäßig verteilt sind, durchläuft der Algorithmus 2/3 des Arrays, bevor alle Elemente in seinen "Bändern" gestreut werden.

Amerikanische Flagge sortieren :: Amerikanische Flagge sortieren

Nun können wir in unseren Erläuterungen zur amerikanischen Multiband-Flagge übergehen.

Wenn wir nicht zwei, nicht drei, sondern eine beliebige Anzahl von Ziffern haben, legen wir fest, wo jede Ziffer beginnen soll (ihr "Band") und zeichnen die Elemente in ihren "Bändern" neu.

In diesem Algorithmus werden Zahlen normalerweise nicht als Dezimalzahl, sondern in einer anderen Bittiefe betrachtet, wobei es sich meistens um eine Zweierpotenz handelt. Häufig wird die Zahl 256 als Grundlage für die Bittiefe verwendet (etwas seltener als 128), sodass Sie die Sortierung effizient anpassen können, um Zeichenfolgen anzuordnen. Bei Zahlen für die Bittiefe ist es zweckmäßiger, kleine 2 ⁿ (2, 4, 16 usw.) zu verwenden, um den Vergleich durch Verschieben um Bits zu ermöglichen, anstatt beim Vergleich von Dezimalzahlen zu einer Potenz zu werden.

Die Animation zeigt ein Beispiel für die Bittiefe mit Basis 16:

1. Suchen Sie beim ersten Durchgang nach dem Maximum, um die maximale Anzahl von Bits unter den Elementen im Array zu bestimmen (um die vom Konto bestimmten Bits korrekt aus den Elementen zu extrahieren).
2. Dann erfolgt eine rekursive Verarbeitung. Beim Aufruf werden die Grenzen des Subarrays und das aktuell verarbeitete Bit angezeigt. Beim ersten Aufruf ist das gesamte Array ein Subarray, das erste Bit links wird genommen.
3. Unter den Elementen des Subarrays wird eine anfängliche Berechnung durchgeführt - wie oft kommt jede Ziffer in der aktuellen Kategorie vor. Mit dieser Anzahl können Sie die Lokalisierung für diese Ziffern der Ziffern bestimmen (dh, die Grenzen und die Position des "Bandes", in das Sie die Elemente verschieben möchten, die die nächste Ziffer in einer bestimmten Ziffer haben, sind bekannt). Tatsächlich sind Lokalisierungen Zeiger auf „Bänder“, in denen die entsprechenden Elemente verschoben werden müssen.
4. Entsprechend den Lokalisierungszeigern findet ein Umtausch vor Ort statt - die Ziffer in der Kategorie zeigt an, wohin Sie den Artikel senden möchten, an dessen Stelle kommt ein weiterer Artikel, mit dem der Umtausch stattgefunden hat. Diese Klausel wird ausgeführt, bis beim nächsten Austausch ein Element, das von einer anderen Stelle ankommt, nicht an seiner Stelle ist (dann können Sie zum nächsten Element des Subarrays übergehen und diese Klausel auf ähnliche Weise für dieses Element ausführen).
5. Nachdem durch den Austausch die Elemente in der nächsten Ziffer durch Zahlen in Blöcke umverteilt wurden, findet eine Rekursion statt - für jeden Block wird derselbe Algorithmus als Subarray angewendet, der nächste als aktuelle Ziffer.

In dem Artikel über das Zählen von Sortierungen mit einer ungefähren Verteilung gibt es einen visuell sehr ähnlichen Algorithmus - die Annäherungssortierung . Dort haben wir gezählt, wie oft jede Zahl im Array vorgekommen ist - und die Elemente entsprechend den erhaltenen Lokalisierungen neu verteilt. Hier zählen wir, wie oft jede Ziffer in der Kategorie für Subarray-Elemente vorkommt - und verteilen die Elemente in dem Subarray entsprechend den erhaltenen Lokalisierungen. Wenn Annäherung eine Art Zählsortierung ist, dann ist "amerikanisch" eine Zählbit-Sortierung.

Ska sort :: Ska sort

Der deutsche Programmierer Malte Skarupke gab bekannt, dass er einen neuen Sortieralgorithmus entwickelt hat, der eine radikal verbesserte „amerikanische Flagge“ darstellt und std :: sort durchschnittlich zweimal übertrifft (std :: sort - ein Algorithmus, der auch als introspektives Sortieren bezeichnet wird) - Ein Hybrid aus schnellem Sortieren und Sortieren nach Haufen .

1. Das Array wird rekursiv sortiert. Auf der ersten Rekursionsebene wird das gesamte Array als Subarray betrachtet.
2. Wenn das Subarray weniger als 128 Elemente enthält, wird std :: sort dafür aufgerufen.
3. Wenn das Subarray 128 bis 1024 Elemente enthält, wird die amerikanische Flaggensortierung dafür aufgerufen.
4. Wenn ein Subarray mehr als 1024 Elemente enthält, wird die Ska-Sortierung dafür aufgerufen.
5. Um den schlimmsten Fall zu vermeiden, wechselt der Algorithmus auch dann zu std :: sort , wenn die rekursive Verschachtelung zu groß ist (mehr als 16 Ebenen), selbst wenn das Subarray mehr als 128 Elemente enthält.

Anscheinend ist es ein sehr effektiver und gleichzeitig äußerst komplexer Algorithmus - die Implementierung des Autors dauert fast anderthalbtausend Zeilen. Vielleicht werden wir diese Sortierung eines Tages in Betracht ziehen, jetzt werden wir nicht mehr darauf eingehen. Interessenten können auf die unten stehenden Links klicken.

Referenzen

Problem der niederländischen Nationalflagge , Art der amerikanischen Flagge

Ska Art: Ich habe einen schnelleren Sortieralgorithmus geschrieben ( Teil 1 , Teil 2 ) Github-Code

Serienartikel:

• Excel-Anwendung AlgoLab.xlsm
• Sortierungen austauschen
• Einfügesortierung
• Nach Auswahl sortieren
• Sortierungen zusammenführen
• Nach Verteilung sortieren
  • Zählsorten mit ungefährer Verteilung
  • Amerikanische Flagge sortieren
  • Suffixbaum in bitweiser Sortierung
  • Sortierungen nach Verteilung vergleichen
• Hybrides Sortieren

In der AlgoLab Excel-Anwendung wurde die Sortierung nach einem zweifarbigen Flag (sortiert Nullen und Einsen), einem dreifarbigen Flag (sortiert Nullen, Einsen und Zweien) und der amerikanischen Flagge angezeigt. Um die „amerikanische Flagge“ zu sortieren, können Sie (in einem Kommentar zu der Zelle mit dem Namen des Algorithmus) das zu verteilende Zahlensystem angeben - der Standardwert ist hexadezimal.