Babylonsort Ein stabiles Hochgeschwindigkeits-Sortierverfahren (Letzte Aktualisierung: 12. August 2025 um 13:56:23 Uhr) Home Daten Name:  Babylonsort Autor:  Martin Oppermann Fertigstellung:  21. September 2021 Veröffentlichung:  - 6. Juli 2025 (Funktionsweise) - ausstehend (Quellcode) Arbeitsweise:  - Teile-und-herrsche - vergleichsbasierend - In-Place rekursiv:  wahlweise stabil:  ja      Inhaltsverzeichnis 1.  Beschreibung 2.  Funktionsprinzip 3.  Wie schnell sortiert Babylonsort? 4.  Messergebnisse (Leistung)   4.1  Standard-Quicksort gegen Stabilisator 5.  Babylonsort starten (Aufruf) 6.  Der rekursive Quellcode   6.4  Rekursion 4: Der Stabilisator (stabilizer) 7.  Hinweise zum Urheberrecht 8.  Finanzielle Unterstützung Beschreibung Babylonsort ist ein von Martin Oppermann als Hobby entwickeltes Sortierverfahren, das stabil sortiert und dessen Entwicklung am 21. September 2021 abgeschlossen wurde. Seitdem wurden jedoch immer wieder Verbesserungen an den Quellcodes vorgenommen. Babylonsort arbeitet nach dem Prinzip Teile und herrsche, sortiert aber trotzdem stabil und kann wahlweise auf- und absteigend sortieren. Babylonsort existiert in zwei verschiedenen Varianten: Die schnellere Variante besteht aus einem einteiligen Quellcode, der seine Arbeitsbereiche selbst verwaltet, sowie aus einer rekursiven Variante, die aus sieben einzelnen Rekursionen besteht, die sich situationsabhängig gegenseitig und selbst aufrufen. Beide Varianten erfordern zur Steuerung des Sortiervorgangs zwei Datenfelder, die jeweils aus der Anzahl von "n" Langzahlen bestehen. Die schnellere Variante benötigt zusätzlich dazu noch zwei kleine Arrays für die Verwaltung der Arbeitsbereiche bei den Haupt- und stabilisierenden Teilungen, die jeweils auf 20 Arbeitsbereiche voreingestellt sind, was für die Sortierung eines Arrays mit etwa 275 Milliarden Datensätzen ausreichen würde. Hierzu muss man noch wissen, dass Babylonsort nur die Positionen der rechten Arbeitsbereiche puffert, weil der aktuell linke durch eine Änderung des rechten Randes und seinen Neustart wiederverwendet wird. Trotz des zusätzlichen Speicherbedarfs an Arrays und Rekursionen, ist Babylonsort trotzdem als In-place-Sortierverfahren anzusehen. Namensgebend war für Babylonsort der Umstand, dass Martin Oppermann einen Namen für sein Sortierverfahren finden musste, der noch nicht bekannt war. Weil das Teile-und-herrsche-Verfahren nachweislich bereits im antiken Babylon bekannt war, hatte er sich dann für den Namen Babylonsort entschieden. Home / Oben Funktionsprinzip Babylonsort arbeitet mit der Technik der verknüpften Datensätze. Bedeutet: Anstelle während der Sortierung immer zwei komplette Datensätze mit ihren ganzen Datenfeldern miteinander zu vertauschen, werden in einem Link-Array lediglich zwei Langzahlen miteinander vertauscht, die stellvertretend für die Positionen der beiden Datensätze im Array stehen. Wenn Babylonsort startet, dann werden im Link-Array diese Verknüpfungen zu den sortierenden Datensätzen erzeugt. Um keine Rechenzeit zu verschwenden, werden diese Zuweisungen bereits als erste Teilung durchgeführt, die drei Teillisten erzeugt (links, identisch, rechts). Die Verknüpfungen in den linken und rechten Teillisten, führen dann je nachdem ob auf- oder absteigend sortiert wird zu Werten in den Datensätzen, die kleiner oder größer als das Vergleichselement sind, das bei Babylonsort grundsätzlich immer in der Mitte der aktuellen Arbeitsbereiche festgelegt wird. Anschließend wird für die linke und rechte Teilliste ein Teile-und-herrsche-Verfahren gestartet, das das Link-Array immer weiter teilt, was ebenfalls jeweils drei Teillisten zum Ergebnis hat. Von den Teilungs-Algorithmen, die die aktuellen Arbeitsbereiche in jeweils drei Teillisten unterteilen, gibt es bei Babylonsort insgesamt vier Stück. Ein fünfter Teilungs-Algorithmus - der "Stabilisator" - ist ausschließlich dafür da, die Verknüpfungszahlen in den mittleren Teillisten (identisch) immer weiter aufsteigend zu teilen, um somit die Stabilität der Sortierung zu gewährleisten. Er wird hierfür von den vier anderen Teilungs-Algorithmen gestartet. Der Stabilisator führt die Teilungen jedoch nur in einer linken (kleiner als) und rechten (größer als) Teilliste durch, weil es jede Verknüpfungszahl im Link-Array nur einmal geben kann. Um Rechenzeit einzusparen starten alle fünf Teilungs-Algorithmen für eine Teilliste jedoch nur dann einen weiteren Teilungs-Algorithmus, wenn diese Teillisten aus mindestens drei Elementen bestehen. Sollten es nur zwei Elemente sein, dann werden diese direkt miteinander verglichen und gegebenenfalls vertauscht. Wenn am Ende der Teilungen im Link-Array die Reihenfolge feststeht, in der sich die Datensätze befinden müssen, dann werden mit Hilfe des Link-Arrays die Zielpositionen der Datensätze bestimmt und die Datensätze anschließend sortiert. Hierbei werden sie von der Position der Sortierschleife aus, direkt zu ihrer Endposition getauscht, wodurch sich die Positionen der Datensätze maximal nur zweimal verändern. Die Sortierschleife läuft hierbei von der Position "links", bis zur Position "rechts - 1" und läuft nur dann weiter, wenn sie sich auf der Position eines Datensatzes befindet, der seine Endposition erreicht hat. Des Weiteren ist noch anzumerken, dass Babylonsort gleich zu Beginn der Sortierung, sowohl bei einer aufsteigenden und auch absteigenden Sortierung in der Lage ist, den Best- und Worst-Case zu erkennen und dementsprechend darauf zu reagieren. Es kann dadurch entweder zur sofortigen Beendigung des Sortiervorgangs, oder zur Spiegelung des Arrays kommen, wobei diese mit einem zweiten Spiegel-Algorithmus auch stabil erfolgen kann, falls es benachbarte identische Elemente geben sollte. Home / Oben Wie schnell sortiert Babylonsort? Babylonsort ist ein vergleichsbasiertes und stabiles Sortierverfahren, das auf dem Teile-und-herrsche-Verfahren basiert. Wenn Teile-und-herrsche-Verfahren die Elemente über weite Entfernungen hinweg direkt miteinander vertauschen, dann können sie zwar grundsätzlich niemals stabil sortieren, weil Babylonsort aber zusätzlich noch mit einem Link-Array arbeitet, in dem sich Verknüpfungszahlen zu den zu sortierenden Datensätzen befinden, stellt Babylonsort mit Hilfe dieser Zahlen die ursprüngliche Reihenfolge der identischen Elemente wieder her. Weil es im Normalfall nicht möglich ist schneller als mit einem Teile-und-herrsche-Verfahren zu sortieren und weil Babylonsort die Positionen der Datensätze des zu sortierenden Arrays maximal nur zweimal verändert, kann man es zumindest bei zufällig gemischten Arrays als gesichert ansehen, dass kein anderes stabiles Sortierverfahren die Geschwindigkeit von Babylonsort erreichen kann. Insbesondere dann, wenn es um eine sehr hohe Anzahl von zu sortierenden Datensätzen geht und diese Datensätze jeweils auch aus einer größeren Anzahl von einzelnen Datenfeldern bestehen, dann wird Babylonsort immer exponentiell schneller als andere Sortierverfahren sein, auch wenn es sich hierbei um sehr schnelle instabile Sortierverfahren, wie zum Beispiel Quicksort handelt. Home / Oben Messergebnisse (Leistung) Herr Oppermann führt aktuell hin und wieder diverse Messungen der Leistungsfähigkeit von Babylonsort durch. Standard-Quicksort gegen Stabilisator: In diesen Tests wurde das Standard-Quicksort (siehe Quellcode) mit dem Stabilisator von Babylonsort verglichen. In den Tests mussten beide Teile-und-herrsche-Verfahren jeweils 1000 zufällig gemischte Link-Arrays mit 10, 100 und 1000 Elementen sortieren, um exakte Vergleichswerte zu erhalten. Bei beiden Teile-und-herrsche-Verfahren wurden sowohl bei der Anzahl der Vergleiche und Vertauschungen, die kleinsten und größten Werte, sowie der Durchschnitt gemessen. Beide Teile-und-herrsche-Verfahren haben hier abwechselnd immer das gleiche zuvor ins Link-Array kopierte Array sortieren müssen, um faire Vergleiche zu erhalten. Bei den Tests hat sich gezeigt, dass der Stabilisator von Babylonsort bei jeder Teilung immer eine Vertauschung mehr durchführen muss, als das Standard-Quicksort, weil der Stabilisator das Vergleichselement immer in der Mitte der Arbeitsbereiche auswählt und dieses zu Beginn immer mit dem letzten Element vertauschen muss. Dafür benötigt das Standard-Quicksort aber im Vergleich zum Stabilisator, bei einer immer größer werdenden Anzahl von Elementen, eine immer größer werdende Anzahl von Vergleichen. Bei nur 1000 Elementen, ist die Anzahl der Vergleiche bereits knapp fünf Mal größer, was auf die bessere Programmstruktur des Stabilisators zurückzuführen ist. 10 Elemente Anzahl der Vergleiche   min. max. ⌀ Standard-Quicksort:  118 472 230 Stabilisator von Babylonsort:  53 149 78 Anzahl der Vertauschungen   min. max. ⌀ Standard-Quicksort:  6 12 9 Stabilisator von Babylonsort:  8 16 12 100 Elemente Anzahl der Vergleiche   min. max. ⌀ Standard-Quicksort:  3706 9086 5520 Stabilisator von Babylonsort:  1131 1825 1351 Anzahl der Vertauschungen   min. max. ⌀ Standard-Quicksort:  140 182 163 Stabilisator von Babylonsort:  170 220 196 1000 Elemente Anzahl der Vergleiche   min. max. ⌀ Standard-Quicksort:  74.176 131.384 90.780 Stabilisator von Babylonsort:  17.326 22.061 18.952 Anzahl der Vertauschungen   min. max. ⌀ Standard-Quicksort:  2285 2477 2386 Stabilisator von Babylonsort:  2616 2816 2719 Home / Oben Babylonsort starten (Aufruf) Um Babylonsort zu starten, müssen beim Aufruf sechs Langzahlen übergeben werden:   Babylonsort L, R, UD, DX, DY, DS Bedeutung der Variablen L Erster zu sortierender Datensatz im Array R Letzter zu sortierender Datensatz im Array UD 0 = aufsteigend... / 1 = absteigend Sortieren DX Erstes zu sortierendes Datenfeld eines Datensatzes DY Letztes zu sortierendes Datenfeld eines Datensatzes DS Sortieren nach diesem Datenfeld der Datensätze Die Aufgabe der Variablen "DX" und "DY" besteht darin, dass man mit ihnen die Möglichkeit hat, nicht alle Datenfelder der Datensätze sortieren zu müssen, sofern die Datenfelder eine numerische Kennzeichnung haben. Dadurch kann man zum Beispiel mehrere Arrays zu einem einzigen zusammenfügen, aber trotzdem alle Teil-Arrays unabhängig voneinander sortieren. Auf Servern steht ja meistens nur eine begrenzte Anzahl von Datenbanken zur Verfügung. Dank der Variablen DX und DY kann man nun alle Datenbanken zu einer zusammenfügen und trotzdem alle unabhängig voneinander sortieren. Die maximale Anzahl der Datenbanken, ist somit nur noch vom zur Verfügung stehenden Speicherplatz abhängig. Beispiel: Datenbank 1: DX = 0 bis DY = 21 Datenbank 2: DX = 22 bis DY = 25 Datenbank 3: DX = 26 bis DY = 33 Und so weiter... Home / Oben Der rekursive Quellcode Vorerst werde ich im Laufe diesen Jahres hier nur nach und nach die Rekursionen der rekursiven Version veröffentlichen, weil diese viel einfacher zu verstehen ist. Der Quellcode besteht aus sieben einzelnen Rekursionen, die sich situationsabhängig gegenseitig, aber auch selbst aufrufen können. Die einteilige Variante von Babylonsort ist zwar deutlich schneller, weil sie ihre Arbeitsbereiche selbst verwaltet, macht jedoch zwingend Sprungadressen erforderlich, damit der Programmablauf direkt zu bestimmten Positionen im Quellcode springen kann. Rekursion 1: (noch nicht veröffentlicht) Rekursion 2: (noch nicht veröffentlicht) Rekursion 3: (noch nicht veröffentlicht) Rekursion 4: Der Stabilisator (stabilizer) (Letztes Update: 8. August 2025 um 17:01:32 Uhr) Sub Babylonsort_Stabilizer(lngL As Long, lngR As Long) ' ==== Babylonsort (stabilizer) ==================================================================== '    Autor: Martin Oppermann '    Datum: 21.9.2021 '  Kontakt: babylonsort@homepage-martin-oppermann.de ' '  Hinweis: In dieser Rekursion wird der aktuelle Arbeitsbereich des Link-Arrays aufsteigend '           geteilt. ' ' Internet: https://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/Babylonsort.php ' ==== Variablen belegen =========================================================================== Dim lngB As Long Dim lngCE As Long Dim lngM As Long Dim lngS As Long Dim lngTEMP As Long ' ==== Das Vergleichselement mit dem letzten vertauschen =========================================== lngM = lngL + Int((lngR - lngL) / 2) lngCE = lngLA(lngM) lngLA(lngM) = lngLA(lngR) lngLA(lngR) = lngCE ' ==== Kleinere Elemente am Anfang des Arbeitsbereiches überspringen =============================== lngS = lngL While lngLA(lngS) < lngCE         lngS = lngS + 1 Wend ' ==== Größere Elemente am Ende des Arbeitsbereiches überspringen ================================== lngB = lngR - 1 While lngL < lngB And lngLA(lngB) > lngCE         lngB = lngB - 1 Wend ' ==== Die Teilung durchführen (falls erforderlich) ================================================ While lngS < lngB ' ---- vorne und hinten vertauschen ----         lngTEMP = lngLA(lngS)         lngLA(lngS) = lngLA(lngB)         lngLA(lngB) = lngTEMP         lngS = lngS + 1         lngB = lngB - 1 ' ---- kleinere Elemente überspringen ----         While lngLA(lngS) < lngCE                 lngS = lngS + 1         Wend ' ---- größere Elemente überspringen ----         While lngLA(lngB) > lngCE                 lngB = lngB - 1         Wend Wend ' ==== Das Vergleichselement gegebenenfalls mit dem Anfang der größeren Elemente vertauschen ======= If lngS < lngR Then         lngLA(lngR) = lngLA(lngS)         lngLA(lngS) = lngCE End If ' ==== Muss der linke Bereich (kleiner) weiter geteilt werden? ===================================== If lngS - lngL > 1 Then         If lngS - lngL > 2 Then                 Babylonsort_Stabilizer lngL, lngB         Else                 If lngLA(lngL) > lngLA(lngB) Then                         lngTEMP = lngLA(lngL)                         lngLA(lngL) = lngLA(lngB)                         lngLA(lngB) = lngTEMP                 End If         End If End If ' ==== Muss der rechte Bereich (größer) weiter geteilt werden? ===================================== If lngR - lngS > 1 Then         If lngR - lngS > 2 Then                 Babylonsort_Stabilizer lngS + 1, lngR         Else                 If lngLA(lngR - 1) > lngLA(lngR) Then                         lngTEMP = lngLA(lngR - 1)                         lngLA(lngR - 1) = lngLA(lngR)                         lngLA(lngR) = lngTEMP                 End If         End If End If End Sub Rekursion 5: (noch nicht veröffentlicht) Rekursion 6: (noch nicht veröffentlicht) Rekursion 7: (noch nicht veröffentlicht) Home / Oben Hinweise zum Urheberrecht Alle Quellcodes von Babylonsort dürfen von allen Personen / Firmen / Unternehmen uneingeschränkt verwendet werden und auch auf andere Internetseiten hochgeladen werden. Sowohl in unveränderter Form, modifiziert, oder an andere Programmiersprachen angepasst. Das schließt auch schriftliche Publikationen in Fachliteratur, Magazinen, Tageszeitungen, Zeitschriften, oder sonstigen Druckerzeugnissen mit ein. In Videos im Internet, oder in Beiträgen / Dokumentationen / Sendungen im Fernsehen / Spielfilmen, dürfen die Quellcodes ebenfalls gezeigt werden. Die Quellcodes bleiben aber trotzdem das geistige Eigentum von Martin Oppermann. Daher möchte Martin Oppermann als Autor genannt werden und es wäre sehr nett, wenn ein Link zu der folgenden Datei auf dieser Internetseite gesetzt / gezeigt werden würde: https://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/Babylonsort.php Home / Oben Finanzielle Unterstützung Sobald der Quellcode von Babylonsort verfügbar ist, bittet Herr Oppermann darum, ihn auf freiwilliger Basis finanziell in seiner Arbeit zu unterstützen, insbesondere dann, wenn Personen, Firmen oder Unternehmen sein Sortierverfahren Babylonsort in der Praxis einsetzen sollten, was aufgrund der Arbeitsgeschwindigkeit ja sehr wahrscheinlich ist. Die dafür erforderliche Bankverbindung, wird hier demnächst zu sehen sein. Aktuell ist eine finanzielle Unterstützung aber noch nicht möglich, weil die dafür erforderliche Gewerbeanmeldung noch nicht vorliegt. Home / Oben / Impressum / Datenschutzerklärung   Diese Internetseite wurde für eine Auflösung von 2160 x 1440 Bildschirmpunkten und eine Anzeige-Skalierung von 150% optimiert.