| SRUDQsort |
(SRUDQsort = simultanrekursives up / down Quicksort)
Hinweis: An dieser Datei wird aktuell noch gearbeitet.
(Ich kann aktuell aus zeitlichen Gründen jeden Tag nur ein wenig daran arbeiten.)
|
Home
|
| Daten |
| Name: |
SRUDQsort |
| Typ: |
Hybrid-Sortierverfahren |
| Autor: |
Martin Oppermann |
| Idee: |
10.9.2021 |
| Programmiert: |
13.9.2021 |
| Veröffentlichung: |
13.9.2021 |
| Arbeitsweise: |
- Out-Of-Place 
- Teile-und-herrsche
- vergleichsbasierend
- verknüpfungsbasierend
|
| rekursiv: |
simultan |
| stabil: |
ja |
|
|
|
|
|
Beschreibung
|
SRUDQsort ist ein schnelles, hybrides und stabil sortierendes Sortierverfahren, das wahlweise auf- (1,2,3,...) oder absteigend (3,2,1,...) sortieren kann.
Auf die Idee zu diesem Sortierverfahren, bin ich am 10.9.2021 während der Arbeit gekommen und ich habe noch am selben Tag mit der Entwicklung begonnen.
Als Basis habe ich leider eine sehr umständliche Lösung für das verwendete "Teile-und-herrsche-Verfahren" programmiert, die die Teilungen jeweils immer mit zwei nacheinander ablaufenden Schleifen realisiert, die die kleineren Elemente erst links und dann die größeren Elemente rechts anordnet.
Alle mit dem Vergleichselement identischen Elemente, verbleiben dabei im Trennungsbereich in der Mitte, was sich hingegen sehr positiv auf die Arbeitsgeschwindigkeit auswirkt.
Eine besonders gute Idee war auch die, auf Rekursionen zu verzichten und anstelle dessen Arbeitsbereiche zu verwenden, die von SRUDQsort selbst verwaltet werden und die Rekursionen dadurch nur simulieren.
Das ist grundsätzlich immer schneller, als mit echten Rekursionen zu arbeiten.
Das "Q" im Namen, mit dem ich an das Sortierverfahren "Quicksort" erinnern wollte, war leider keine gute Idee, weil SRUDQsort - wie ich heute weiß - mit Quicksort praktisch keinerlei Gemeinsamkeiten hat.
Die Art wie SRUDQsort seine Arbeitsbereiche teilt, hat nämlich nur teilweise Ähnlichkeit mit Quicksort.
Tatsächlich basiert SRUDQsort auf einem aus dem antiken Babylon stammenden Algorithmus, der aus der "binären Suche" weiterentwickelt wurde, die wissenschaftlich belegt, ebenfalls aus diesem Zeit stammt.
Aus diesem Grund habe ich den Nachfolger von SRUDQsort, der aus einer ganzen Vielzahl diverser Verbesserungen am Quellcode entstanden ist, auch den Namen "Babylonsort" gegeben.
Home
/
Oben
|
Funktionsbeschreibung
|
SRUDQsort arbeitet nach dem "Teile-und-herrsche-Verfahren" und wählt in der Mitte des aktuellen Arbeitsbereiches ein Vergleichselement aus.
Alle Elemente die kleiner als dieses Vergleichselement sind, werden dann links im Arbeitsbereich angeordnet und alle Elemente die größer als dieses Vergleichselement sind, rechts im Arbeitsbereich.
Die Elemente, die mit dem Vergleichselement identisch sind, bilden dann in der Mitte den Trennungsbereich.
Der linke Bereich (kleiner), sowie der rechte Bereich (größer), werden dann jeweils zu neuen Arbeitsbereichen und mit dem gleichen Algorithmus immer weiter geteilt, bis die Sortierung beendet ist.
SRUDQsort arbeitet hierbei jedoch nicht mit Rekursionen und verwaltet anstelle dessen seine Arbeitsbereiche selbst.
| (!) |
Die Funktionsweise von diesem Algorithmus, wird Sachkundige zwar zugegeben stark an Quicksort erinnern, jedoch ist dieser Algorithmus von seiner Grundidee her dem Quicksort gegenüber haushoch überlegen, weil er in optimalen Fällen und bei sehr großen Anzahlen von zu sortierenden Elementen, theoretisch um ein vielfaches schneller sortieren kann.
Insbesondere dann, wenn es sehr viele identische Elemente gibt.
SRUDQsort kommt hier jedoch nicht auf so hohe Geschwindigkeiten, weil es dafür nicht optimal genug programmiert ist.
Der Nachfolger von SRUDQsort - das Sortierverfahren "Babylonsort" - erreicht diese Geschwindigkeiten in günstigen Fällen jedoch problemlos.
|
|
|
Zu Beginn kopiert SRUDQsort alle zu sortierenden Elemente in ein "Out-Of-Place"-Array und erstellt dabei in einem Link-Array Verknüpfungen, die sich auf die zu sortierenden Elemente beziehen.
Parallel dazu wird noch überprüft, ob der "Best-Case" oder der "Worst-Case" vorliegen.
Im Fall des "Best-Case" (bester Fall) braucht SRUDQsort nicht zu sortieren und beendet sich selbst.
Und im Fall des "Worst-Case" (schlechtester Fall) spiegelt SRUDQsort lediglich den Arbeitsbereich und beendet sich anschließend ebenfalls.
Während der eigentlichen aufsteigenden (1,2,3,...) Sortierung, vergleicht SRUDQsort über die Verknüpfungen im Link-Array, die zu sortierenden Elemente.
Gegebenenfalls müssen dadurch jeweils immer nur zwei Verknüpfungszahlen vertauscht werden und nicht immer zwei komplette Datensätze.
Der Vorteil für die Arbeitsgeschwindigkeit, steigt hier mit der Anzahl der jeweiligen Elemente in den einzelnen Datensätzen an.
Wenn die Sortierung der Verknüpfungen im Link-Array beendet ist, folgt anschließend gegebenenfalls noch eine Korrektur der zuvor verlorengegangenen Stabilität.
Hierbei wird nach Bereichen mit identisch großen Elementen gesucht.
In diesen Bereichen werden die Verknüpfungszahlen dann ebenfalls mit dem "Teile-und-herrsche-Verfahren" aufsteigend (1,2,3,...) sortiert.
Wenn eine absteigende (3,2,1,...) Sortierung gewünscht ist, wird dieser Bereich anschließend noch gespiegelt, was damit zusammenhängt, weil die Datensätze bei einer absteigenden Sortierung, vom "Out-Of-Place"-Array aus, im letzten Schritt spiegelverkehrt ins Array zurückkopiert werden.
Durch diese doppelte Spiegelung, bleibt die Stabilität dann erhalten.
Im letzten Schritt werden die zu sortierenden Elemente vom "Out-Of-Place"-Array aus, zum Array zurückkopiert.
Die Reihenfolge wird hierbei von den Verknüpfungszahlen im Link-Array gesteuert.
Abhängig davon ob auf- (1,2,3,...) oder absteigend (3,2,1,...) sortiert werden soll, geschieht dies im Array entweder von links nach rechts, oder von rechts nach links.
Home
/
Oben
|
Der Quellcode
Version vom 16.1.2023
Sub SRUDQsort[field Array, L, R, UD, RX, RY, RS]
; ==== SRUDQsort (simultanrekursives up / down Quicksort) ==========================================
;
; Name: SRUDQsort
; Typ: Hybrid-Sortierverfahren
; Autor: Martin Oppermann
; Idee: 10.9.2021
; Programmiert: 13.9.2021
; Veröffentlichung: 13.9.2021
; Version vom: 16.1.2023
; Arbeitsweise: - Out-Of-Place
; - Teile-und-herrsche
; - vergleichsbasierend
; - verknüpfungsbasierend
; rekursiv: simultan
; stabil: ja
; Siehe: http://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/SRUDQsort.php
;
;
; Array[ <<DATENSATZNUMMER>> , <<REIHE EINES DATENSATZES>> ]
;
; Das Link-Array LI[#] und das "Out-Of-Place"-Array OOP[#, ##] müssen entsprechend der Größe des
; zu sortierenden Arrays dimensioniert werden.
;
;
; Aufruf:
; Call SRUDQsort[L , R , UD , RX , RY , RS]
;
; ---- Die 6 Startwerte ----
; L: Beginn links im Array
; R: Ende rechts im Array
; UD: 0 = aufsteigend sortieren (1,2,3,...)
; 1 = absteigend sortieren (...,3,2,1)
; RX: erste Reihe in einem Datensatz (zum Beispiel 0)
; RY: letzte Reihe in einem Datensatz (zum Beispiel 4)
; RS: sortieren nach Reihe # in einem Datensatz
;
; Achtung!
; - Die Variablen "LI(#)" und "OOP(#,##)", müssen entsprechend der maximal zu erwartenden Größe, des
; zu sortierenden Teils des Arrays dimensioniert werden.
; - Das Sortierverfahren kann an vier Stellen vorzeitig beendet werden (siehe "Exit Sub")
;
; ==== Schritt 1: Startschutz und Variablen belegen ================================================
If R - L < 1 Then Exit Sub
If RX > RY Or RS < RX Or RY < RS Then Exit Sub
Dim LI[999999] As Long
Dim OOP[999999, 10] As Long
Dim SRA[5000, 1] As Long
If UD <> 0 Then UD = 1
BC = 1
OD = -1
SR = 0
SRA[0, 0] = 0
SRA[0, 1] = R - L
WC = 1
; ==== Schritt 2: Das Array in das "Out-Of-Place"-Array kopieren ===================================
; ==== und auf den Best- und Worst-Case überprüfen ===================================
For X = L To R
; ---- Das Array in das "Out-Of-Place"-Array kopieren ----
OD = OD + 1
For Y = RX To RY
OOP[OD, Y] = Array[X, Y]
Next Y
; ---- Die Link-Werte erstellen (Verknüpfungen und Hilfe bei der Stabilisierung) ----
LI[OD] = OD
; ---- Auf den Best- / Worst-Case überprüfen ----
If X < R And BC = 1 Then
If UD = 0 Then
If Array[X, RS] > Array[X + 1, RS] Then BC = 0
Else
If Array[X, RS] < Array[X + 1, RS] Then BC = 0
End If
End If
If X < R And WC = 1 Then
If UD = 0 Then
If Array[X, RS] <= Array[X + 1, RS] Then WC = 0
Else
If Array[X, RS] >= Array[X + 1, RS] Then WC = 0
End If
End If
Next X
; ---- Best-Case = Es gibt nichts zu sortieren = beenden ----
If BC = 1 Then Exit Sub
; ---- Worst-Case = Es gibt nichts zu sortieren = Das Array spiegeln und dann beenden ----
If WC = 1 Then
For X = 0 To Int[[R - L + 1] / 2] - 1
For Y = RX To RY
TEMP = Array[L + X, Y]
Array[L + X, Y] = Array[R - X, Y]
Array[R - X, Y] = TEMP
Next Y
Next X
Exit Sub
End If
; ==== Schritt 3: Das Array aufwärts und instabil sortieren ========================================
; ---- Die nächste simultane Rekursion starten ----
SRUDQsort_start_recursions:
If SR < 0 Then GoTo SRUDQsort_stabilizer
LL = SRA[SR, 0]
RR = SRA[SR, 1]
SR = SR - 1
; ---- Die aktuelle simultane Rekursion aufwärts und instabil teilen ----
SRUDQsort_divide:
B = RR + 1
M = OOP[LI[LL + Int[[RR - LL + 1] / 2]], RS]
S = LL - 1
; ---- kleiner ----
For X = LL To RR
If OOP[LI[X], RS] < M Then
S = S + 1
If S < X Then
TEMP = LI[S]
LI[S] = LI[X]
LI[X] = TEMP
End If
End If
Next X
; ---- größer ----
For X = RR To S + 1 Step -1
If OOP[LI[X], RS] > M Then
B = B - 1
If X < B Then
TEMP = LI[X]
LI[X] = LI[B]
LI[B] = TEMP
End If
End If
Next X
; ---- Die nächsten simultanen Rekursionen erzeugen ----
; ---- größer ----
If B < RR Then
SR = SR + 1
SRA[SR, 0] = B
SRA[SR, 1] = RR
End If
; ---- kleiner ----
If LL < S Then
RR = S
GoTo SRUDQsort_divide
End If
GoTo SRUDQsort_start_recursions
; ==== Schritt 4: Benachbarte identische Werte stabilisieren =======================================
SRUDQsort_stabilizer:
If RX = RY Then GoTo SRUDQsort_copy
SY = -1
SRUDQsort_stabilizer_new_loop:
SX = SY
SRUDQsort_stabilizer_loop:
If SX = OD Then GoTo SRUDQsort_copy
SX = SX + 1
If SX < OD Then
If OOP[LI[SX], RS] = OOP[LI[SX + 1], RS] Then
SY = SX + 1
TEMP = 0
Do
If SY < OD Then
If OOP[LI[SX], RS] = OOP[LI[SY + 1], RS] Then
SY = SY + 1
Else
TEMP = 1
End If
Else
TEMP = 1
End If
Loop Until TEMP = 1
GoTo SRUDQsort_stabilizer_sort
End If
End If
GoTo SRUDQsort_stabilizer_loop
; ---- Benachbarte identische Werte, durch die Link-Werte stabilisieren ----
SRUDQsort_stabilizer_sort:
SR = 0
SRA[0, 0] = SX
SRA[0, 1] = SY
; ---- Die nächste simultane Rekursion starten ----
SRUDQsort_stabilizer_start_recursions:
If SR < 0 Then
If UD = 1 Then
For X = 0 To Int[[SY - SX + 1] / 2] - 1
TEMP = LI[SX + X]
LI[SX + X] = LI[SY - X]
LI[SY - X] = TEMP
Next X
End If
GoTo SRUDQsort_stabilizer_new_loop
End If
LL = SRA[SR, 0]
RR = SRA[SR, 1]
SR = SR - 1
; ---- Die aktuelle simultane Rekursion stabil teilen ----
SRUDQsort_stabilizer_divide:
M = LL + Int[[RR - LL + 1] / 2]
TEMP = LI[M]
LI[M] = LI[RR]
LI[RR] = TEMP
M = TEMP
S = LL - 1
; ---- kleiner ----
For X = LL To RR - 1
If LI[X] < M Then
S = S + 1
If S < X Then
TEMP = LI[S]
LI[S] = LI[X]
LI[X] = TEMP
End If
End If
Next X
; ---- größer ----
B = S + 2
LI[RR] = LI[S + 1]
LI[S + 1] = M
; ---- Die nächsten simultanen Rekursionen erzeugen ----
; ---- größer ----
If B < RR Then
SR = SR + 1
SRA[SR, 0] = B
SRA[SR, 1] = RR
End If
; ---- kleiner ----
If LL < S Then
RR = S
GoTo SRUDQsort_stabilizer_divide
End If
GoTo SRUDQsort_stabilizer_start_recursions
; ==== Schritt 5: Die Datensätze in das Array zurückkopieren =======================================
SRUDQsort_copy:
If UD = 0 Then
; ---- aufwärts kopieren (UD = 0) ----
For X = 0 To OD
For Y = RX To RY
Array[L + X, Y] = OOP[LI[X], Y]
Next Y
Next X
Else
; ---- abwärts kopieren (UD = 1) ----
For X = 0 To OD
For Y = RX To RY
Array[R - X, Y] = OOP[LI[X], Y]
Next Y
Next X
End If
End Sub
|
|
|
Home
/
Oben
|
| Index der Variablen |
| (alphabetisch) |
|
| Variable |
Erklärung |
| Array[#, #] |
Das zu sortierende Array
Das Array enthält die zu sortierenden Datensätze.
|
| B |
 bigger /  größer
Die Variable "B" enthält am Ende des aktuellen simultanen Rekursionsbereichs die Position, wo die Verknüpfungen (Link-Array "LI[#]") zu den Elementen beginnen, die größer als das Element in der Mitte (Variable "M") sind.
Bis das erste größere Element gefunden wurde, liegt die Position der Variable "B", eine Position nach dem aktuellen simultanen Rekursionsbereich (Variable "LL" bis "RR").
|
| BC |
Best-Case / bester Fall
Die Variable "BC" enthält den Status, ob der "Best-Case", der "beste Fall" vorliegt.
Darunter versteht man die Situation, dass der zu sortierende Bereich des Arrays, bereits sortiert ist.
Liegt der "Best-Case" vor, dann hat die Variable "BC" den Wert 1.
Ansonsten ist der Wert 0.
Wenn aufsteigend (1,2,3,...) sortiert wird, dann darf kein nachfolgendes Element kleiner als das vorherige sein.
Und wenn absteigend (...,3,2,1) sortiert wird, dann darf kein nachfolgendes Element größer als das vorherige sein.
In beiden Fällen würde die Variable "BC" auf den Wert 0 gesetzt werden.
|
| L |
Links im Array
Die Variable "L" enthält die Position des ersten zu sortierenden Datensatzes im Array.
|
| LI[#] |
Link-Array / Verknüpfungs-Array
Das Link-Array enthält die Verknüpfungen zu den zu sortierenden Datensätzen im "Out-Of-Place"-Array (OOP[#, #]).
Diese Verknüpfungen bestehen aus Zahlen, die die Positionen der Datensätze enthalten.
Bei der eigentlichen Sortierung sortiert SRUDQsort die Datensätze nicht direkt, sondern vorerst nur die Verknüpfungszahlen im Link-Array.
Bei der vergleichsbasierenden Bewertung der Elemente, gibt das Link-Array mit seinen Verknüpfungszahlen vor, welche Datensätze verglichen werden müssen.
Zum Schluss steuert das Link-Array mit seinen Verknüpfungszahlen, in welcher Reihenfolge die Datensätze vom "Out-Of-Place"-Array, ins Array zurückkopiert werden.
Unabhängig davon, ob das Array vollständig oder nur zum Teil sortiert werden soll, beginnen die Verknüpfungen im Link-Array immer bei Position 0.
Werden im Array zum Beispiel nur die Datensätze 98 bis 160 sortiert, dann befinden sich die Verknüpfungen im Link-Array, auf den Positionen 0 bis 62.
Der besondere Vorteil einer verknüpfungsbasierenden Sortierung besteht darin, dass nicht immer zwei komplette Datensätze vertauscht werden müssen, sondern nur zwei Verknüpfungszahlen.
Bestehen die zu sortierenden Datensätze zum Beispiel aus jeweils 20 Einzeldaten, dann macht das Link-Array die Sortierung damit 20 Mal schneller.
|
| LL |
Anfang des aktuellen simultanen Rekursionsbereichs
Die Variable "LL" enthält die Position der ersten Verknüpfung im zu sortierenden Link-Array, die zum aktuellen simultanen Rekursionsbereich gehört.
|
| M |
Mitte (Haupt-Sortierung)
Die Variable "M" enthält den Wert des Elements, zu dem die mittlere Verknüpfung (Link-Array "LI[#]") im aktuellen simultanen Rekursionsbereich, zu Beginn der Teilung geführt hat.
Alle Verknüpfungen die zu kleineren Elementen als die Variable "M" führen, werden während der Teilung zur linken Seite (Variable "S") des aktuellen simultanen Rekursionsbereichs getauscht und alle größeren zur rechten Seite (Variable "B").
| (!) |
Die Variable "M" ist bei der Haupt-Sortierung kein "Pivotelement", weil die Variable "M" für keine feste Position steht, von der eine Teilung ausgeht.
Anstelle dessen werden alle zu sortierenden Verknüpfungen im aktuellen simultanen Rekursionsbereich, über die verknüpften Datensätze mit dem Wert der Variable "M" verglichen.
Weil es mehrere Elemente geben kann, die mit dem Wert der Variable "M" identisch sein können, ist diese Art der Teilung der Pivot-Methode gegenüber deutlich vorteilhafter.
|
|
Mitte (stabilisierende Sortierung)
Wenn der Stabilisierer über die Verknüpfungen (Link-Array "LI[#]") in den Datensätzen mindestens zwei benachbarte identische Elemente gefunden hat, dann müssen alle Verknüpfungen die zu diesem Bereich führen, ihren Verknüpfungszahlen entsprechend aufsteigend (1,2,3,...) sortiert werden, damit die bei der Haupt-Sortierung eventuell verlorengegangene Stabilität, wiederhergestellt wird.
Die Variable "M" enthält hierfür im aktuellen simultanen Rekursionsbereich zu Beginn der Teilung zuerst die Position der mittleren Verknüpfung und gibt damit vor, welche Verknüpfung mit der letzten Verknüpfung getauscht werden muss.
Anschließend bekommt die Variable "M" die Verknüpfungszahl der letzten Verknüpfung.
Alle Verknüpfungen mit kleineren Verknüpfungszahlen als die Variable "M", werden dann während der Teilung zur linken Seite (Variable "S") des aktuellen simultanen Rekursionsbereichs getauscht.
Weil es jede Verknüpfungszahl nur einmal geben kann, braucht anschließend die letzte Verknüpfung nur die Verknüpfungszahl der Verknüpfung rechts neben der linken Seite (Variable "S") anzunehmen (LI[RR] = LI[S + 1]) und diese die Verknüpfungszahl der Variable "M" (LI[S + 1] = M).
Die Variable "B", die für die größere rechte Seite steht, bekommt die Position zwei Positionen rechts von der linken Seite (B = S + 2).
Damit kann die Teilung der größeren Seite, immer in nur drei Schritten durchgeführt werden.
| (!) |
Die Variable "M" ist zu Beginn der Teilung ein Pivotelement, wird dann aber unmittelbar nach dem Vertauschen der mittleren und letzten Verknüpfung, zu einem Vergleichselement, das dann wie bei der Haupt-Sortierung funktioniert. |
|
| OD |
outsourced datasets / ausgelagerte Datensätze
Die Variable "OD" enthält die Anzahl der zu sortierenden Datensätze im Array.
Diese Anzahl ist immer um den Wert 1 kleiner, als die tatsächliche Anzahl.
Das liegt daran, weil die zu sortierenden Datensätze vor der Sortierung in das "Out-Of-Place"-Array (OOP[#, #]) kopiert werden, wo sich der erste Datensatz immer auf der Position 0 befindet.
|
| OOP[#, #] |
"Out-Of-Place"-Array / Array der ausgelagerten Datensätze
Das "Out-Of-Place"-Array enthält die vom zu sortierenden Array, ausgelagerten Datensätze.
Vor der Sortierung werden diese Datensätze zuerst in das "Out-Of-Place"-Array kopiert und nachdem die Verknüpfungen (Link-Array "LI[#]") zu diesen Datensätzen sortiert wurden, werden die Datensätze in der richtigen Reihenfolge in das Array zurückkopiert.
| Vorteil: |
Alle zu sortierenden Datensätze im Array, müssen sich während der Sortierung nur zweimal bewegen, wodurch die Sortierung sehr schnell abläuft. |
| Nachteil: |
Für die Sortierung ist sehr viel zusätzlicher Speicherplatz erforderlich.
Im schlimmsten Fall +100%.
Weil mehr Arbeitsspeicher jedoch bedeutend weniger kostet, als eine schnellere Rechenleistung, kann dieser Nachteil vernachlässigt werden.
|
Unabhängig davon, ob das Array vollständig oder nur zum Teil sortiert werden soll, beginnen die ausgelagerten Datensätze im "Out-Of-Place"-Array immer bei Position 0.
Werden im Array zum Beispiel nur die Datensätze 98 bis 160 sortiert, dann befinden sich die ausgelagerten Datensätze im "Out-Of-Place"-Array, auf den Positionen 0 bis 62.
|
| R |
Rechts im Array
Die Variable "R" enthält die Position des letzten zu sortierenden Datensatzes im Array.
|
| RR |
Ende des aktuellen simultanen Rekursionsbereichs
Die Variable "RR" enthält die Position der letzten Verknüpfung im zu sortierenden Link-Array, die zum aktuellen simultanen Rekursionsbereich gehört.
|
| RS |
Reihe "#" sortieren
Die Variable "RS" gibt vor, nach welcher Reihe die Datensätze im Array sortiert werden sollen.
| (!) |
Dass hier von "Reihen" die Rede ist liegt daran, weil es einfacher ist sich die Funktionsweise eines Sortierverfahrens in der Form vorzustellen, dass alle Datensätze nebeneinander (horizontal) in Spalten angeordnet sind.
Die Einzeldaten der jeweiligen Datensätze, bilden dadurch Reihen.
|
|
| RX |
Reihe von "#"
Die Variable "RX" gibt vor, mit welcher Reihe die Einzeldaten der Datensätze im Array beginnen.
Für gewöhnlich beginnen Datensätze zwar immer bei der Reihe 0, aber um einen möglichst großen Komfort in den Benutzungs- und Anwendungsmöglichkeiten zu realisieren, gibt SRUDQsort hier die Möglichkeit, auch andere Reihen zu nennen.
Damit ist es dann auch möglich, beliebig viele Arrays in den Reihen eines einzigen Arrays untereinander zu vereinen und sie trotzdem unabhängig voneinander sortieren zu können.
Anwendungsbeispiel:
Wenn man eine Internetseite mit einer begrenzten Anzahl von Datenbanken betreibt, dann kann man alle Datenbanken zu einer einzigen zusammenfügen und alle Datenbanken immer noch unabhängig voneinander sortieren.
| (!) |
Dass hier von "Reihen" die Rede ist liegt daran, weil es einfacher ist sich die Funktionsweise eines Sortierverfahrens in der Form vorzustellen, dass alle Datensätze nebeneinander (horizontal) in Spalten angeordnet sind.
Die Einzeldaten der jeweiligen Datensätze, bilden dadurch Reihen.
|
|
| RY |
Reihe bis "#"
Die Variable "RY" gibt vor, mit welcher Reihe die Einzeldaten der Datensätze im Array enden.
| (!) |
Dass hier von "Reihen" die Rede ist liegt daran, weil es einfacher ist sich die Funktionsweise eines Sortierverfahrens in der Form vorzustellen, dass alle Datensätze nebeneinander (horizontal) in Spalten angeordnet sind.
Die Einzeldaten der jeweiligen Datensätze, bilden dadurch Reihen.
|
|
| S |
smaller / kleiner
Die Variable "S" enthält am Anfang des aktuellen simultanen Rekursionsbereichs die Position, wo die Verknüpfungen (Link-Array "LI[#]") zu den Elementen enden, die kleiner als das Element in der Mitte (Variable "M") sind.
Bis das erste kleinere Element gefunden wurde, liegt die Position der Variable "S", eine Position vor dem aktuellen simultanen Rekursionsbereich (Variable "LL" bis "RR").
|
| SR |
Anzahl der simultanen Rekursionen
Die Variable "SR" enthält die Anzahl der simultanen Rekursionen, im Rekursions-Array (SRA[5000, 1]).
Diese Anzahl ist immer um den Wert 1 kleiner, als die tatsächliche Anzahl.
Das liegt daran, weil die simultanen Rekursionen im Rekursions-Array, immer auf der Position 0 beginnen.
|
| SRA[5000, 1] |
Array der simultanen Rekursionen
Das simultane Rekursions-Array enthält die Anfangs- und Endpositionen, der aktuell aktiven simultanen Rekursionen.
"SRA[#, 0]" steht hierbei für den Anfang und "SRA[#, 1]" für das Ende der jeweiligen simultanen Rekursionen.
Anfang und Ende beziehen sich jedoch nicht auf die Positionen der zu sortierenden Datensätze, sondern auf die Positionen der zu sortierenden Verknüpfungen im Verknüpfungs-Array (Link-Array "LI[#]").
Die Verwaltung der jeweiligen simultanen Rekursionen geschieht in der Form, dass neue simultane Rekursionen immer hinten an das Rekursions-Array angehängt werden.
Wenn eine weitere simultane Rekursion gestartet werden muss, dann startet immer die hintere im Rekursions-Array, wobei beim Start der betreffende Eintrag im Rekursions-Array gelöscht wird.
Wenn das Rekursions-Array leer ist (SR = -1), dann ist die Sortierung beendet.
Zum Anhängen von neuen simultanen Rekursionen an das Rekursions-Array wäre noch anzumerken, dass immer nur die rechten Seiten (größer als...) der Teilungen angehängt werden.
Die linken Seiten (kleiner als...) werden immer direkt gestartet, ohne vorher an das Rekursions-Array übergeben worden zu sein.
Hierbei wird bei der aktuell aktiven simultanen Rekursion, nachdem sie beendet ist, das Ende des Arbeitsbereichs auf den Wert des Endes der linken Seite (kleiner als...) geändert (RR = S) und der Programmablauf springt direkt zurück zum Beginn der Teilung, wodurch die aktuell aktive simultane Rekursion, ein weiteres Mal verwendet wird.
| (!) |
Die Anzahl von maximal 5000 gleichzeitig aktiven simultanen Rekursionen, orientiert sich an der früheren Anzahl der maximal gleichzeitig aktiven Rekursionen im "Visual Basic", von Microsofts Tabellenkalkulation "Excel".
Irgendwann zwischen Sommer 2021 und Mitte März 2022, wurde die Größe dieses Stapelspeichers durch Microsoft auf 2748 reduziert.
Im realen Betrieb wird man mit SRUDQsort aber wohl nie 5000 aktive simultane Rekursionen erreichen können.
Selbst wenn man eine Million zufällig erzeugte Zahlen sortiert, liegt die maximale Anzahl der gleichzeitig aktiven simultanen Rekursionen, nur zwischen 23 und 34.
Bei 10 Millionen Zahlen sind es zwischen 29 und 39 und bei 40 Millionen zwischen 32 und 44.
(Als Test wurden jeweils 1000 Mal, entsprechend der jeweiligen Anzahl, zufällig erzeugte Zahlen sortiert.
Dieser Test wurde auf einem alten Notebook als Langzeitmessung mit einem Excel-Makro durchgeführt, um festzustellen, mit wie vielen gleichzeitig aktiven simultanen Rekursionen, in der Praxis in etwa zu rechnen ist.
Der Test begann am 28.3.2022 um 13:10 Uhr und dauerte 85 Stunden und 56 Minuten.)
|
| (!) |
Simultane Rekursionen arbeiten grundsätzlich immer schneller als echte Rekursionen.
Wie groß der Unterschied in der Geschwindigkeit ausfällt, lässt sich aber nicht genau sagen, weil das von vielen Details abhängt.
Zu nennen wären da die Art des Computers, das verwendete Betriebssystem, die verwendete Programmiersprache und auch die Art der Programmierung der Software.
Im Fall von "Visual Basic" in Microsofts Tabellenkalkulation "Excel", konnten bei Vergleichsmessungen unter Windows 10, in der Vergangenheit höhere Arbeitsgeschwindigkeiten von bis zu 78% gemessen werden.
Weil der für die Rekursionen zuständige Teil von "Visual Basic" zwischen Sommer 2021 und Mitte März 2022 deutlich verbessert wurde, arbeiten simultane Rekursionen aktuell nur noch 27% bis 33% schneller und in sehr seltenen Fällen auch bis zu 50%.
Des Weiteren wäre noch anzumerken, dass simultane Rekursionen auch weniger Arbeitsspeicher / Systemressourcen benötigen und in fast jeder Programmiersprache programmiert werden können.
Um unsinnige Quellcodes zu vermeiden, sollte der Programmablauf mit Sprungmarken oder Zeilennummern, direkt zu bestimmten Positionen im Quellcode springen können.
|
|
| SX |
Die Erklärung folgt demnächst
|
| SY |
Die Erklärung folgt demnächst
|
| TEMP |
temporary auxiliary variable / temporäre Hilfsvariable
Die Variable "TEMP" ist eine Hilfsvariable, die für die Vertauschung von zwei Elementen benötigt wird, weil es in den meisten Programmiersprachen keinen Befehl dafür gibt, die Inhalte von zwei Elementen direkt zu vertauschen.
Für gewöhnlich wird die Variable "TEMP" wie folgt in drei Schritten verwendet:
|
| UD |
"up" or "down" sort / auf- oder abwärts sortieren
Die Variable "UD" gibt vor, ob der mit den Variablen "RX" und "RY" festgelegte Bereich im Array, auf- (1,2,3,...) oder absteigend (...,3,2,1) sortiert werden soll.
Für eine aufsteigende Sortierung hat die Variable "UD" den Wert 0 und für eine absteigende Sortierung den Wert 1.
| UD = 0 |
(aufsteigend sortieren / 1,2,3,...) |
| UD = 1 |
(absteigend sortieren / ...,3,2,1) |
|
| WC |
Worst-Case / schlechtester Fall
Die Variable "WC" enthält den Status, ob der "Worst-Case", der "schlechteste Fall" vorliegt.
Darunter versteht man die Situation, dass der zu sortierende Bereich des Arrays, genau spiegelverkehrt zur gewünschten Sortierung ist.
Liegt der "Worst-Case" vor, dann hat die Variable "WC" den Wert 1 und der Bereich wird anschließend gespiegelt.
Ansonsten ist der Wert 0.
Wenn aufsteigend (1,2,3,...) sortiert wird, dann darf kein nachfolgendes Element größer oder identisch mit dem vorherigen sein.
Und wenn absteigend (...,3,2,1) sortiert wird, dann darf kein nachfolgendes Element kleiner oder identisch mit dem vorherigen sein.
In beiden Fällen würde die Variable "WC" auf den Wert 0 gesetzt werden.
|
| X |
Schleifen (waagerecht)
Die Variable "X" steht für waagerecht laufende Schleifen.
Die Schleifen laufen von Position "A" zu Position "B" und bei jedem Durchlauf enthält die Variable "X", dann die entsprechende Position.
Meistens laufen die Schleifen vorwärts, aber in einem Fall auch rückwärts.
|
| Y |
Schleifen (senkrecht)
Die Variable "Y" steht für senkrecht laufende Schleifen, die die einzelnen Reihen (Einzeldaten) der zu sortierenden Datensätze ansteuern.
Die Schleifen laufen von Position "A" (Variable "RX") zu Position "B" (Variable "RY") und bei jedem Durchlauf enthält die Variable "Y", dann die entsprechende Position.
|
|
|
|
Home
/
Oben
|
Hinweise zum Urheberrecht
|
Alle Codes von SRUDQsort, 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 Codes ebenfalls gezeigt werden.
Die Codes bleiben aber trotzdem mein geistiges Eigentum.
Daher möchte ich - Martin Oppermann - als Autor genannt werden und es wäre schön, wenn ein Link zu der folgenden Datei auf meiner Internetseite gesetzt werden würde:
http://www.homepage-martin-oppermann.de/Informatik/Sortierverfahren/SRUDQsort.php
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. |
|
|
|
|