Sortieralgorithmen

In Datenbanken muss man sich über die Sortierung von Datensätzen gemeinhin keine Gedanken machen. Die Engines enthalten alles Benötigte, um Daten in Abfragen oder auch Recordsets über einfache SQL-Statements sortiert auszugeben. Doch hin und wieder steht man vor der Aufgabe, auch Daten in Arrays zu sortieren, etwa, um sie einem Treeview oder einem Listenfeld zu verabreichen. Über die möglichen Algorithmen erfahren Sie hier mehr.

Beispieldatenbank

Die Beispiele dieses Artikels finden Sie in der Datenbank 1702_Sorting.zip.

Sortieren per VBA

Einen kleinen Vorgeschmack lieferte bereits der Beitrag zu BubbleSort der Doppelausgabe 01/2016. Dieser Algorithmus ist ziemlich simpel und durchschaubar. Er hat aber seine Grenzen erreicht, sobald es um die Performance geht. Bei umfangreichen Datenbeständen ist er extrem langsam. Hier sind Alternativen gefragt.

Eigentlich kommt es ziemlich selten vor, dass Daten per VBA sortiert werden müssen. Sie liegen ja in der Regel in Tabellen vor, und die lassen sich über Abfragen sortieren. Manchmal jedoch kommen sie aus externen Quellen, wie etwa Textdateien. Natürlich könnte man diese in Tabellen importieren, dann einer Sortierabfrage unterziehen und das Ergebnis, so benötigt, wieder im VBA-Projekt über ein Recordset auslesen. Eleganter ist es aber, diesem Umweg zu vermeiden und die Daten direkt per VBA zu sortieren. Legen Sie sich dazu einfach ein Modul mit generellen Sortieralgorithmen an, wie in der Beispieldatenbank geschehen, das Sie später gegebenenfalls in ihre Zieldatenbank kopieren können.

Ausgangslage: String-Array

Der häufigste Fall ist sicher das Sortieren von Texten eines String-Arrays. Um diesen Anwendungsfall mit den im Folgenden vorgestellten Algorithmen zu testen, wird ein gefülltes String-Array mit einer nicht zu geringen Anzahl von Einträgen benötigt. Wir holen sie einfach aus einer vorliegenden Kundentabelle. Die Hilfsfunktion CreateStringArray (siehe Listing 1) stellt es zur Verfügung.

Private Function CreateStringArray(Optional Limit As Long) As String()
     Dim rs As DAO.Recordset
     Dim S As String
     Dim n As Long
     Dim arrRet() As String
     Set rs = CurrentDb.OpenRecordset("SELECT Nachname, Vorname" & _
         "FROM tblKunden ORDER By ID", dbOpenDynaset)
     Do While Not rs.EOF
         If (Len(rs!Nachname.Value) > 2) And _
            (Len(rs!Vorname.Value) > 2) Then
             S = rs!Nachname.Value & ", " & rs!Vorname.Value
             ReDim Preserve arrRet(n)
             arrRet(n) = S
             n = n + 1
         End If
         If Limit <> 0 Then If n > Limit Then Exit Do
         rs.MoveNext
     Loop
     rs.Close
     CreateStringArray = arrRet
End Function

Listing 1: Über diese Funktion werden die Daten einer Kundentabelle in ein String-Array überführt

Hier werden die Felder Nachname und Vorname der Tabelle tblKunden in ein Recordset aufgenommen, das nach der ID der Datensätze sortiert ist. Die Namen selbst sind damit unsortiert. Eine Schleife durchläuft alle Datensätze und berücksichtigt nur jene, in der die Namen mindestens drei Buchstaben enthalten. In der Variablen S werden dann Nachname und Vorname, durch Komma getrennt, aneinandergefügt. Dieses Ergebnis wird jeweils einem Element des Arrays arrRet zugewiesen, dessen Dimension sich ständig über die Zählvariable n erweitert, wobei die ReDim-Anweisung den Inhalt nicht zerstört, weil sie eine Preserve-Klausel enthält. Optional können Sie der Prozedur per Parameter ein Limit übergeben, welches die Anzahl der Elemente des Ergebnis-Arrays begrenzt. Ohne Limit kommt es zu etwa 9.000 Elementen.

Sie rufen diese Funktion etwa so auf:

Dim arr() As String
arr = CreateStringArray()
... (Sortieren von arr() ) ...

Hier handelt es sich um ein eindimensionales Array. Nachname und Vorname stehen nicht in getrennten Feldern. Letzteres würde ein zweidimensionales Array erfordern und damit auch kompliziertere Sortieralgorithmen. Der Trick des Verkettens von Nach- und Vorname über ein Trennzeichen sortiert aber automatisch korrekt nach beiden Feldern, soweit zufällig nicht in einem Nachnamen ein Komma enthalten ist. Nun kann es an das Sortieren des Test-Arrays gehen.

Wizhook

Access-VBA hält an sich keine Funktion vor, um eine solches Array zu sortieren. Tatsächlich existiert jedoch eine Methode eines versteckten Klassenobjekts, die das ermöglicht. Blenden Sie im Objektkatalog per Kontextmenü die Verborgenen Elemente ein, so finden Sie die Klasse Wizhook in ihm, bei der es sich um eine Sammlung von Funktionen zu verschiedensten Aspekten handelt. Sie müssen kein Objekt dieser Klasse neu erzeugen, da Access sie von sich aus instanziiert. Der Beweis im VBA-Direktfenster:

  Wizhook Is Nothing
-> Falsch

Eine Methode der Klasse lautet SortStringArray mit dieser Definition:

Sub SortStringArray(Array() As String)

Zu übergeben ist ihr also ein String-Array, das allerdings eindimensional sein muss. Sie sortiert das Array auch wunschgemäß. Das aber erst, nachdem die Klasse freigegeben wurde! Denn ohne einen geheimen Schlüssel funktionieren keine der Funktionen des Wizhook-Objekts. Sie schalten sie erst über das Setzen der Key-Eigenschaft frei. Wozu Microsoft das implementiert hat, ist ein Rätsel, denn dieser Zahlenschlüssel ist natürlich keineswegs geheim:

Sub SortWizHook(sarr() As String)
     WizHook.Key = 51488399
     WizHook.SortStringArray sarr
End Sub

Die Methoden dieser Klasse wurden übrigens mit jeder neuen Access-Version erweitert. Sie sind nicht dokumentiert, und auch einige Seiten im Netz konnten nur einen Teil der Funktionen analysieren.

Der Key wird hier bei jedem Aufruf der Funktion SortWizHook gesetzt. Das ist allerdings nicht wirklich notwendig. Einmal gesetzt bleibt die Klasse für die gesamte VBA-Sitzung freigeschaltet. Die korrekte Funktion können Sie nun etwa so testen:

Dim arr() As String
Dim i As Long
arr = CreateStringArray()
SortWizHook arr
For i = 0 To Ubound(arr)
     Debug.Print arr(i)
Next i

Im VBA-Direktfenster listen sich nun alle Namen des Arrays alphanumerisch aufsteigend auf. Der Wizhook-Methode kann nicht angegeben werden, ob auf- oder absteigend sortiert werden soll. Das hat sie auch mit den meisten der folgenden Algorithmen gemein. Wäre eine absteigende Sortierung gewünscht, so müsste diese anschließend über ein erneutes Umsortierung mit einer Hilfsfunktion erreicht werden:

Sub SortReverse (arr() As String)
     Dim arrRet() As String
     Dim n As Long, i As Long
     
     n= UBound(arr)
     Redim arrRet(n)
     For i = 0 To n
         arrRet(i) = arr(n-i)
     Next i
End Sub

Das tut der Performance keinen Abbruch und verläuft ziemlich schnell.

BubbleSort

Der Vollständigkeit halber bilden wir den BubbleSort-Algorithmus nochmals in Listing 2 ab. Jedes Element des Arrays sarr wird ausnahmslos mit jedem verglichen. Ist das eine größer, als das andere, so kommt es zum Vertauschen der beiden über die temporäre Variable S. Eine absteigende Sortierung erhalten Sie hier durch Änderung der Vergleichszeile:

Sub BubbleSortStrings(sarr() As String)
     Dim S As String
     Dim i As Long, j As Long, n As Long
     
     n = UBound(sarr)
     For i = 0 To n - 1
         For j = i + 1 To n
             If sarr(i) > sarr(j) Then
                 S = sarr(i)
                 sarr(i) = sarr(j)
                 sarr(j) = S
             End If
         Next j
     Next i
End Sub

Listing 2: Funktion zum Sortieren über BubbleSort

If sarr(i) < sarr(j) Then

Bei den 9.000 Elementen des Beispiel-Arrays kommt es hier zu über 40 Millionen Iterationen. Das beansprucht auch auf einem aktuellen Rechner ziemlich viel Rechenzeit. Wir haben bei uns 13 Sekunden gemessen – ein völlig inakzeptabler Wert! Die Wizhook-Methode erreichte dasselbe Ergebnis in nur 0,03 Sekunden!

Sehen wir, ob sich dieser Wert durch andere Methoden noch unterbieten lässt.

QuickSort

Dieser Algorithmus ist zweifellos der verbreitetste überhaupt. Es ist davon auszugehen, dass auch die Wizhook-Methode, wie auch die Database Engine, ihn intern verwenden. Seine Effizienz ist kaum zu überbieten. Der Witz an ihm ist der Umstand, dass er ausgerechnet dann am schnellsten ist, wenn die Daten möglichst unsortiert daher kommen. Sind die Daten bereits weitgehend vorsortiert, dann ist er recht langsam!

Der Algorithmus in Listing 3 arbeitet rekursiv. Das heißt, dass sich die Funktion fortwährend selbst aufruft, wie an den letzten beiden Zeilen zu erkennen ist. Die jeweiligen Elementzeiger stehen in den Variablen LR und LL, stellvertretend für Rechter Zeiger und Linker Zeiger.

Public Sub QuickSortStrings(sarr() As String, Optional ByVal LL As Long, Optional ByVal LR As Long)
     Dim n1 As Long, n2 As Long
     Dim sTmp As String, sSwap As String
     If LR = 0 Then   LL = LBound(sarr): LR = UBound(sarr)
     n1 = LL: n2 = LR
     sTmp = sarr((LL + LR) \ 2)
     Do
         Do While (sarr(n1) < sTmp) And (n1 < LR)
             n1 = n1 + 1
         Loop
         Do While (sTmp < sarr(n2)) And (n2 > LL)
             n2 = n2 - 1
         Loop
         If n1 <= n2 Then
             sSwap = sarr(n1)
             sarr(n1) = sarr(n2)
             sarr(n2) = sSwap
             n1 = n1 + 1
             n2 = n2 - 1
         End If
     Loop Until n1 > n2
     If LL < n2 Then QuickSortStrings sarr, LL, n2
     If n1 < LR Then QuickSortStrings sarr, n1, LR
End Sub

Listing 3: Funktion zum Sortieren über Quicksort

Das Prinzip besteht darin, dass die Daten zunehmend hälftig in Blöcke unterteilt und dann jeweils nur die Elemente eines Blocks untersucht werden. Und die Blöcke werden immer kleiner, bis sie nur noch aus zwei Elementen bestehen. Das schränkt die Anzahl der Vergleiche stark ein.

Sie übergeben der Funktion nur das Array und lassen die beiden optionalen Parameter unberücksichtigt:

Dim arr() As String
arr = CreateStringArray()
QuickSortStrings arr

Username or Email

Passwort

Angemeldet bleiben