Interaktive Demo
Patiencesort-Visualisierung
Patiencesort ist nach der Kartenpatience benannt. Jede Karte kommt auf den linkesten Stapel mit größerer oberster Karte. Dann wird immer wieder die kleinste oberste Karte eingesammelt, bis alle Stapel leer sind.
Wähle „Umgekehrt“: Alles landet auf einem einzigen Stapel. Bei „Sortiert“ beginnt jede Karte einen eigenen Stapel.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element im Array
- Karte, die gelegt wird
- Karte auf einem Stapel
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Umgekehrte Eingaben ergeben einen einzigen Stapel, der einfach von oben abgetragen wird.
Mittlerer Fall
O(n log n)
Binäre Suche über die Stapel, dann eine Prioritätswarteschlange der obersten Karten: log n Schritte pro Element.
Schlechtester Fall
O(n log n)
Selbst bei n Stapeln braucht jedes Element mit einer Prioritätswarteschlange nur log n Vergleiche.
Zusätzlicher Speicher
O(n)
Jedes Element liegt auf einem Stapel außerhalb des Arrays.
Stabil
Ja
Hier liegen gleiche Elemente nie aufeinander, und bei Gleichstand kommt der linke Stapel zuerst.
In-place
Nein
Die Stapel entstehen außerhalb des Arrays.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort diese Seite | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Stapel auslegen
Jede Karte kommt auf den linkesten Stapel mit größerer oberster Karte; gibt es keinen, beginnt sie rechts einen neuen. Die obersten Karten bleiben dadurch von links nach rechts sortiert, deshalb findet eine binäre Suche den richtigen Stapel.
2. Einsammeln
Jeder Stapel ist von oben nach unten sortiert. Die kleinste aller obersten Karten ist also das nächste Element des sortierten Arrays. Hier werden die obersten Karten nacheinander verglichen; effiziente Versionen halten sie in einer Prioritätswarteschlange (einem Heap) für log n Vergleiche pro Element.
3. Längste aufsteigende Teilfolge
Die Zahl der Stapel ist genau die Länge der längsten aufsteigenden Teilfolge der Eingabe. Deshalb wird das Auslegen auch für sich allein genutzt, zum Beispiel beim Vergleichen von Versionen einer Textdatei.