Sortieren mit der Lawine

Datensortierung: Avalanchesort besser als Quicksort?
Keine Kommentare

Wer Daten sortieren möchte, greift in den meisten Fällen wohl auf Algorithmen wie Quicksort oder Mergesort zurück. Mit Avalanchesort gibt es nun darüberhinaus eine rekursive Variante, Entwickler Dr. Dieter Porth stellt den neuen Ansatz vor.

Wer effizient sortieren will, der findet in Lehrbücher meist zwei Algorithmen beschrieben: Quicksort und Mergesort. Bessere Lehrbücher erwähnen auch Naturell Mergesort. Quicksort braucht zum Sortieren im besten Fall so viele Vergleiche wie Mergesort in der Regel. Naturell Mergesort ist im Vergleich oft rund 20% besser als Quicksort im besten Fall. Die Zahl der Vergleiche bei Mergesort ist dabei eine Grenze, mit welcher beim Naturell Mergesort im schlimmsten Fall rechnen muss, weil der Naturell-Mergesort im Gegensatz zu Mergesort oder Quicksort die Vorsortierung ausnutzt. Der Naturell Mergesort bestimmt im ersten Schritt sortierte Teilfolgen (= Runs) und mergt diese. Im Internet sind für den Naturell Merge hauptsächlich iterative Varianten zu finden. Zur Abgrenzung dagegen habe ich meine aufsteigend rekursive Variante Avalanchesort genannt. Die Lawine (=engl.: avalanche) beschreibt , wie die sortierte Menge an Daten wie bei einer Lawine klein startet und explosiv anwächst.


So wie eine Lawine nicht weiß, wie viel Schnee hangabwärts noch zu finden ist, muss der Avalanchesort im Gegensatz zu Quicksort oder Mergesort nicht wissen, wie viele Daten er sortieren soll. Dies liegt an der aufsteigend rekursiven Steuerung des Saccharosetransporters. Eine unsortierte Datenmenge wird nach folgenden Ablauf sortiert: Der Avalanchesort-Starter beginnt mit dem Rekursionsindex 1 und ruft einen Avalanchesort mit der Ordnung 1 auf. Dieser mergt er zwei Runs (= sortierte Teillisten) der 0. Ordnung zu einem Run 1. Ordnung. Wenn noch Unsortiertes übrig ist, ruft der Starter einen zweiten Avalanchesort mit Ordnung 1 auf. Der Avalanchesort liefert ein zweiten Run 1. Ordnung zurück. Der Starter mergt die beiden Runs 1. Ordnung zu einem Run 2. Ordnung und erhöht gleichzeitig seinen internen Rekursionsindex auf 2. Wenn immer noch Unsortiertes übrig ist, startet er einen Avalanchesort mit der Ordnung 2. Dieser ruft zwei Avalanchesorts der Ordnung 1 auf und mergt deren Runs der Ordnung 1 zu einem Run der Ordnung 2. Der Starter mergt das Ergebnis zusammen mit den zuvor schon generierten Run der Ordnung 2 zu einem Run der Ordnung 3. Der Starter erhöht seinen Rekursionsindex solange, bis alles sortiert ist. Die Abbildung zeigt, wie lawinenartig mit Anstieg des Rekursionsindex die Gier nach Sortierdaten wächst. Zusammenfassend kann man sagen: Der Starter zählt die Klassenordnung solange hoch, bis das rekursive Avalanchesort das letzte Datum durch Mergen von zwei Run gleicher Klasse sortieren konnte.

International PHP Conference

Passwords are so 1990

by Sam Bellen (Auth0)

Domain-Driven PHP

by Henning Schwentner (WPS – Workplace Solutions)

JavaScript Days 2020

Architektur mit JavaScript

mit Golo Roden (the native web)


Auf Github ist der Sortieralgorithmus unter porthd/avalanchesort als PHP-Code veröffentlicht. Wie beim PHP-Befehl usort erlaubt Avalanchesort die Nutzung eigener Vergleichsfunktionen. Im Gegensatz zu usort unterstützt Avalanchesort auch mehrfaches Sortieren. Eine stabile Sortierung liegt vor, wenn eine Liste nach zwei Sortierungen bzgl. Vorname bzw. Nachname so aufgebaut ist, dass, wie im Adressbuch bei gleichen Nachnamen, auch die Vornamen sortiert vorliegen. Der Test testAvalanchesortStable zeigt, dass Avalanchesort stabil sortiert, während testUsortUnstable zeigt, dass die PHP-Funktion usort beim zweiten Sortieren die erste Sortierung zerschießen kann. Mit diesem Artikel verbinde ich die Hoffnung, dass PHP vielleicht doch noch irgendwann eine stabile Alternative zum instabilen Quicksort in seinen Sortierbefehlen bekommt. Zur Titelfrage: Ich denke, Avalanchesort ist besser als Quicksort, weil es stabil sortiert und vergleichbar effizient bei Vergleichen und Datentransfers ist.

Bei der Programmierung wurde auch die Datenhaltung vom Algorithmus getrennt, damit man leicht per Interface Injection dem Sortierverfahren verschiedene Datenhaltungsklassen zuweisen kann. Die Testergebnisse zeigen, dass Avalanchesort mit weniger Vergleichen auskommt als Quicksort. Im Gegensatz dazu braucht Quicksort im unsortierten Fall weniger Datenvertauschungen als Avalanchesort. Diese Effizienz erkauft es vermutlich mit dem Verlust an Sortierstabilität.

In Bezug auf die Datenhaltung enthält die Programmierung zwei Varianten: eine für Arrays und eine für Listenarray. Der Listenarray kombiniert die Idee der Array-Indexierung und die Idee der Nachbarschaftsbeziehung von Listen. Wie beim Array kann über einen Index direkt auf das Feld mit seinen Elementdaten zugegriffen werden. Wie bei einer Liste kann aber auch über Prev- und Next-Verweise direkt zum Nachbarn gewechselt werden. Die zweite Variante habe ich programmiert, weil sich in Listen der Aufwand für Speicherveränderungen reduziert. Im Quicksort für Arrays muss man die Array-Elemente vertauschen. Im Avalanchesort für Listen braucht man nur die Zeiger auf Elementen vertauschen. Es gibt sogar eine Variante, mit welcher man die sortierte Liste in einen natürlichen Array umordnen kann.

Die Trennung zwischen Datenhaltung und Algorithmus lässt noch einen Unterschied zwischen Avalanchesort und Quicksort offenbar werden. Quicksort braucht „Array“-artige Datenstrukturen, um in der zu sortierenden Liste leicht vor und zurückgehen zu können. Avalanchesort kommt dagegen mit einfachen Listen aus. Der Ansatz wäre deshalb vermutlich auch in der Lage, über mehreren Rechner verteilte Datenlisten effizient zu sortieren, wenn dies nötig ist.

Unsere Redaktion empfiehlt:

Relevante Beiträge

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu:
X
- Gib Deinen Standort ein -
- or -