|
|
 |
|
 |
|
 |
 |
|
Hilfe zum Thema: Excel, Wert
 SplitSort - Aufteilen, bis nichts mehr geht
Alle wesentlichen noch heute verwendeten Sortieralgorithmen sind schon vor Jahrzehnten entwickelt worden. Dennoch bemühen sich seither viele kluge Köpfe immer wieder darum, neue Methoden zu finden. Aufgrund der Tatsache, dass da nichts weltbewegendes mehr herausgekommen ist, kann man von einem Amateur wie mir wohl erst recht keine Sensationen erwarten.
Trotzdem macht es freilich Spass, immer mal wieder etwas auszuprobieren, vielleicht stößt man ja rein zufällig auf eine sensationelle Entdeckung :-)
Bei meinen Experimenten kam u.a. "SplitSort" heraus. Ich habe mir diesen Namen zwar ausgedacht, aber ich bin mir ziemlich sicher, dass die Methode so oder so ähnlich schon von hunderten Informatikern vor mir "erfunden" worden ist (obwohl ich sie nirgendwo im Netz gefunden habe).
Im Grunde handelt es sich um ein Mischmasch aus QuickSort und MergeSort. SplitSort "splittet" wie diese das Array in zwei Teile und benutzt zur Entscheidung, welches Element wo hinkommt, wie QuickSort ein Pivotelement. Allerdings werden hier keine einzelnen Werte miteinander vertauscht, sondern zwei temporäre Arrays angelegt. Alle Werte, die kleiner oder gleich wie das Pivotelement sind, kommen in das erste, alle anderen in das zweite temporäre Array. Das ist sozusagen das umgekehrte Reißverschlussprinzip von Mergesort. Dann werden die beiden Teilarrays nacheinander an zwei rekursive Instanzen der Prozedur übergeben (eigentlich werden die Teilarrays vorher wieder in das Hauptarray zurückgeschrieben und dieses wird komplett als Referenz übergeben, aber das verwirrt in der Beschreibung. Jede rekursive Instanz untersucht nämlich nur einen bestimmten Teil der Gesamtmenge, daher kann man sich das ruhig so vorstellen, als wenn das Array geteilt wurde).
SplitSort "splittet" wie Merge- und QuickSort immer weiter auf, bis nur noch ein einzelnes Element in einer Instanz "ankommt". Wenn die Teilbereiche "zurückkommen", sind die Elemente darin in sich komplett sortiert, so dass (wie bei QuickSort) dann keine weitere Aktion mehr nötig ist.
Das Verfahren brachte beim Testen einige Probleme zum Vorschein. Das wichtigste: Wenn eine Teilmenge leer ist, sind alle Werte in der anderen Teilmenge. Wird diese an die nächste Instanz übergeben, passiert dort das Gleiche: Die eine Menge ist 0, die andere beinhaltet alle Werte. Folglich wird die Menge mit den Werten immer so weitergereicht, bis es zum Stapelüberlauf kommt. Durch wechselndes (zufälliges) Wählen des Pivotelements könnte man vielleicht Abhilfe schaffen, aber wenn alle Werte in so einer Menge gleich groß sind, nutzt das auch nichts. Außerdem könnte dann keine Stabilität erreicht werden (siehe dazu weiter unten).
Ich habe das Problem wie folgt gelöst: Als Pivotelement wird stets der letzte Wert des untersuchten Bereiches gewählt und durch den Vergleich
If aDaten(x) <= vglWert Then ...
befindet er sich nach der Sortierung immer in der ersten Teilmenge. Wenn es also zu dem Fall kommt, dass eine Menge leer ist, dann kann das nur die zweite sein!
In diesem Fall ist i (der Zähler der ersten Menge) identisch mit m (Anzahl der untersuchten Elemente). Mit der vielleicht nicht gleich einleuchtenden Konstruktion
If i = m Then
i = m - 1
Else
....
End If
wird dafür gesorgt, dass das letzte Element der ersten Menge (welches gleichzeitig das größte ist!) nachträglich der zweiten Menge zugeordnet und das Array doch noch geteilt wird.
SplitSort sieht in der Animation mit Zufallszahlen aus wie QuickSort, hat aber ein Merkmal, welches QuickSort nicht hat: Es ist (wie MergeSort) stabil, das heißt: Elemente gleichen Wertes behalten ihre ursprüngliche Reihenfolge. Von daher wäre SplitSort in angepasster Form zur Sortierung von Datensätzen bzw. Listen geeignet.
SplitSort ist bei zufällig verteilten Werten etwas langsamer als seine beiden Vorbilder, aber von meinen "selbsterfundenen" Algorithmen der mit Abstand schnellste!
Bei anormal verteilten Werten (z.B. wenn die Ausgangsliste absteigend sortiert ist) hat SplitSort jedoch eine sehr schlechte Laufzeit, da dann die Rekursionstiefe sehr schnell steigt. Bei etwa 5000 Werten wird es in diesem Falle crashen ("Nicht genügend Stapelspeicher"), weshalb Splitsort für den Einsatz in der Praxis ungeeignet ist. Es war halt nur ein Experiment. :-)
Sub SplitSort(aDaten(), ByVal a As Long, ByVal e As Long)
Dim x As Long, i As Long, j As Long, m As Long
Dim vglWert, aDatenTemp1(), aDatenTemp2()
m = e - a + 1
If m > 1 Then
ReDim aDatenTemp1(m), aDatenTemp2(m)
vglWert = aDaten(e)
For x = a To e
If aDaten(x) <= vglWert Then
i = i + 1
aDatenTemp1(i) = aDaten(x)
Else
j = j + 1
aDatenTemp2(j) = aDaten(x)
End If
Next
If i = m Then
i = m - 1
Else
For x = 1 To m
If x <= i Then
aDaten(a + x - 1) = aDatenTemp1(x)
Else
aDaten(a + x - 1) = aDatenTemp2(x - i)
End If
Next
End If
Call SplitSort(aDaten(), a, a + i - 1)
Call SplitSort(aDaten(), a + i, e)
End If
End Sub
Code eingefügt mit Syntaxhighlighter 3.0
|
Google-Anzeigen
|
|
 |
Geschickt von rlx, Do 01.05.2008 2:11
|
 |
 |
|
