In den Kommentaren zu früheren Artikeln gibt es gelegentlich Vorwürfe - warum sollten Sie auch andere Sortierungen studieren, wenn es bereits die schnellste schnelle Sortierung der Welt gibt? Sie sagen, dass all diese phantasievollen Exoten keinen Nutzen haben und niemand braucht.


Percy Diaconis , der Solitairesortierung entlang und quer studiert hat, glaubt, dass dies der schnellste Weg ist, ein Kartenspiel manuell anzuordnen.

Wenn also ein angesehener Mathematiker (und ein erfahrener Kartenmagier) nicht lügt, ist mit dem praktischen Wert des Algorithmus alles in Ordnung.

Beobachten Sie jetzt Ihre Hände.

Stufe 1. Stapel legen

Also nimm die Würmer vom Deck. Sie repräsentieren eine Reihe von dreizehn zufälligen Elementen.



Wir müssen die Karten in mehrere Stapel zerlegen, damit die Karten in jedem Stapel eine geordnete Reihenfolge haben.

Mit anderen Worten, unsere Aufgabe in dieser Phase ist es, schnell mehrere geordnete Subarrays aus dem vorhandenen unsortierten Array zu erstellen. Gleichzeitig ist es sehr wünschenswert, dass die Anzahl dieser Subarrays kleiner ist, was bedeutet, dass wir uns bemühen müssen, sicherzustellen, dass die Subarrays echter sind. Dies geschieht wie folgt.

Die erste Karte ist der Anfang des ersten Stapels.



Wir übertragen nacheinander Karten auf diesen Stapel, bis die nächste übertragene Karte kleiner ist als die oberste im Stapel.

Außerdem ist jeder Stapel ein Stapel - wir arbeiten nicht mit dem gesamten Stapel, sondern nur mit der obersten Karte, die zuletzt gelegt wurde.



Wenn die aktuelle Karte mehr als das Minimum im Stapel ist, müssen Sie einen neuen Stapel erstellen. Die aktuelle Karte öffnet einen neuen Stapel.



Die Reihenfolge der Stapel ist wichtig! Wenn ihre Anzahl bereits mehr als eins beträgt, legen wir die nächste Karte nicht auf den letzten Stapel, sondern auf den Stapel ganz links, in den wir sie legen können.

Jetzt, nach der Dame, muss ich irgendwo eine Neun anbringen. Mechanisch möchte ich die Karte in den zweiten Stapel legen, aber im ersten Stapel ist die oberste Karte mehr als neun. So können wir den ersten Stapel fortsetzen, ohne seine Reihenfolge zu verletzen. Die nächsten drei, die übrigens auch den neun folgen, gehen zum ersten Stapel.



Sieben und sechs können nicht zum ersten Stapel hinzugefügt werden (sie sind größer als die oberste Karte darin), aber sie haben immer noch einen Platz im zweiten Stapel.



Ace startet einen neuen Stapel. Die verbleibende Kleinigkeit fällt in verschiedene Fächer, je nachdem, wie weit links der Stapel war, in den er eingesetzt werden konnte.



Infolgedessen werden die Karten in mehreren Stapeln ausgelegt. In jedem Stapel sind die Karten eine absteigende Reihenfolge, oben befindet sich die kleinste Karte. Stapel sind Stapel.

Da wir zuerst versucht haben, die Stapel links auszufüllen, haben wir die kleinstmögliche Menge gebildet. Wenn wir nur um das Array herumgehen und die abnehmenden Subarrays daraus extrahieren würden, würde der Haufen natürlich viel größer werden.

Stufe 2. Die unterste Reihe

Bewegen Sie die verfügbaren obersten Karten etwas nach unten, sodass sie in einer separaten Reihe stehen. Wenn die Stapel Stapel sind, arbeiten wir mit der unteren Reihe wie mit einer Warteschlange.



Wichtig ist, dass die obersten Karten, die in den Stapeln verfügbar sind, auch eine geordnete Reihenfolge sind. Die untere Reihe ist bereits in aufsteigender Reihenfolge sortiert. Was nicht verwunderlich ist - beim Bilden von Kartenstapeln wurden kleinere Karten nach links geschickt.

Bis zum Ende der Sortierung sind wir in Zukunft nicht mehr an allen Karten interessiert, die auf dem Tisch liegen. Nur diese werden benötigt:

• Die Karte ganz links (nennen wir sie die aktuelle) in der unteren Reihe der Warteschlange.
• In Stacks-Stacks arbeiten wir nur mit den besten verfügbaren Karten. In diesem Fall werden nur die Stapel benötigt, die sich direkt auf der aktuellen Karte und links befinden. Stapel, die sich zu diesem Zeitpunkt rechts befinden, werden nicht benötigt.

In der unteren Reihe sortieren wir die Karten von links nach rechts. Ganz links ist das aktuelle Minimum, wir bringen es in die ursprüngliche obere Reihe zurück. Gleichzeitig ist es jedes Mal, wenn wir eine andere Karte zur Basis zurückkehren, notwendig, eine andere an ihre Stelle zu setzen. Woher bekommt man es? Von den Stapeln, die sich über der aktuellen Karte und links davon befinden, wird unter den verfügbaren Karten ein Minimum ausgewählt, das sich zur freien Position der aktuellen linken Karte in der unteren Reihe und von dort zum Hauptarray bewegt.

Zwei im Array kehren sofort zurück. Der frei gewordene Platz wird vom Triple eingenommen (wir verschieben ihn vom ersten Stapel in die unterste Reihe), und von der unteren Reihe geht das Triple mindestens zum Hauptarray. In den ersten beiden Stapeln wird das Minimum erneut gesucht - dies sind die vier - was auch nach Hause geht. Fünf wird das aktuelle Minimum usw.



Wenn wir die Arbeit sehr schnell mit einer aufsteigenden Reihenfolge der Warteschlange und einer absteigenden Reihenfolge der Stapel kombinieren, erhalten wir alle Elemente vom Minimum bis zum Maximum. So etwas im Allgemeinen.

Animation dieses Prozesses.



Wenn Sie alle oben genannten Punkte in Python übersetzen, erhalten Sie Folgendes:

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles]) 

Referenzen

Geduldssortierung ( Google-translate )

Quelle zum Sortieren von Geduld

Princeton CS: Am längsten zunehmende Folge

Kombinatorik der Geduld beim Sortieren von Stapeln ( Google-translate )

Wiki-Abstracts: Patientensortierung

Word Aligned ( Google-Übersetzung )

Serienartikel:

• Excel-Anwendung AlgoLab.xlsm
• Sorte austauschen
• Insertion Sorts
  • Bibliothekar Sort
  • Solitaire Sort
  • Sortieren Sie "Turm von Hanoi"
  • Junge Tischsortierung
  • Sortierung umkehren
  • Sortiervergleich einfügen
• Nach Auswahl sortieren
• Sortierungen zusammenführen
• Nach Verteilung sortieren
• Hybridsortierung

In der AlgoLab-Anwendung ist diese Sortierung jetzt aktiv. Gleichzeitig ist die Visualisierung in zwei Modi möglich: in Form von Karten (Standardmodus) und einfach in Form von Zahlen. Für den Kartenstil ist es jedoch erforderlich, dass der Unterschied zwischen den maximalen und minimalen Elementen im Array weniger als 54 beträgt (die Anzahl der Karten im Deck, einschließlich zweier Joker). Wenn diese Bedingung nicht erfüllt ist oder der Kartenmodus vollständig deaktiviert ist (dazu müssen Sie im Kommentar für die Zelle mit dem Sortiernamen card = 0 schreiben), erfolgt die Visualisierung in Form von stumpfen Ziffern.

Die Anzüge werden in der Reihenfolge ihres bevorzugten Dienstalters betrachtet: Peaks <Clubs <Tamburine <Herzen.


Das heißt, jede Karte eines Tamburinanzugs eines Tamburins ist größer als jede Karte eines Clubanzugs, jede Karte eines Herzanzugs ist größer als jede Karte eines Spitzenanzugs usw. Wenn wir eine Analogie mit Zahlen ziehen, dann sind die Spitzen von 0 bis 9, die Keulen von 10 bis 19, die Diamanten von 20 bis 29, die Herzen von 30 bis 39 (ja, natürlich beträgt die Anzahl der Karten innerhalb der Farbe nicht genau zehn, aber Sie verstehen, was gemeint ist). Das Dienstalter innerhalb der Klage wird normal sein: von Zwei bis Ass. Sie können auch die Joker nehmen, die älter sind als alle anderen Karten. In diesem Fall ist der rote Joker schwerer als der schwarze.

Dieser Artikel wurde mit Unterstützung von EDISON Software verfasst, einem professionellen Webentwicklungsunternehmen , das kürzlich seine Website neu gestaltet hat.