title image


Smiley 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 VergleichIf aDaten(x) 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 Ifwird 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) 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 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 IfEnd Sub Code eingefügt mit Syntaxhighlighter 3.0


mfg

Ralf

Der Computer löst Probleme, 
die es ohne ihn nicht gäbe!



geschrieben von

Anhang
Bild 45336 zu Artikel 1913277

Login

E-Mail:
  

Passwort:
  

Beitrag anfügen

Symbol:
 
 
 
 
 
 
 
 
 
 
 
 
 

Überschrift: