{"id":55000351,"date":"2017-04-01T00:00:00","date_gmt":"2017-04-01T00:00:00","guid":{"rendered":"http:\/\/access-basics.de\/351"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-30T00:00:00","slug":"Sortieralgorithmen","status":"publish","type":"post","link":"https:\/\/access-basics.de\/index.php\/Sortieralgorithmen.html","title":{"rendered":"Sortieralgorithmen"},"content":{"rendered":"

\"\"<\/p>\n

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.<\/p>\n

Beispieldatenbank<\/h2>\n

Die Beispiele dieses Artikels finden Sie in der Datenbank 1702_Sorting.zip<\/b>.<\/p>\n

Sortieren per VBA<\/h2>\n

Einen kleinen Vorgeschmack lieferte bereits der Beitrag zu BubbleSort<\/b> 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.<\/p>\n

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.<\/p>\n

Ausgangslage: String-Array<\/h2>\n

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<\/b> (siehe Listing 1) stellt es zur Verfügung.<\/p>\n

Private Function <\/span>CreateStringArray(Optional<\/span> Limit As Long<\/span>) As String<\/span>()\r\n     Dim <\/span>rs As <\/span>DAO.Recordset\r\n     Dim <\/span>S As String<\/span>\r\n     Dim <\/span>n As Long<\/span>\r\n     Dim <\/span>arrRet() As String<\/span>\r\n     Set<\/span> rs = CurrentDb.OpenRecordset(\"SELECT Nachname, Vorname\" & _\r\n         \"FROM tblKunden ORDER By ID\", dbOpenDynaset)\r\n     Do While<\/span> Not<\/span> rs.EOF\r\n         If (Len<\/span>(rs!Nachname.Value) > 2) And _\r\n            (Len<\/span>(rs!Vorname.Value) > 2) Then\r\n             S = rs!Nachname.Value & \", \" & rs!Vorname.Value\r\n             ReDim Preserve arrRet(n)\r\n             arrRet(n) = S\r\n             n = n + 1\r\n         End If<\/span>\r\n         If <\/span>Limit <> 0 Then If n > Limit Then<\/span> Exit Do<\/span>\r\n         rs.MoveNext<\/span>\r\n     Loop<\/span>\r\n     rs.Close\r\n     CreateStringArray = arrRet\r\nEnd Function<\/span><\/pre>\n
Listing 1: Über diese Funktion werden die Daten einer Kundentabelle in ein String-Array überführt<\/p>\n
Hier werden die Felder Nachname<\/b> und Vorname<\/b> der Tabelle tblKunden<\/b> in ein Recordset aufgenommen, das nach der ID<\/b> 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<\/b> werden dann Nachname<\/b> und Vorname<\/b>, durch Komma getrennt, aneinandergefügt. Dieses Ergebnis wird jeweils einem Element des Arrays arrRet<\/b> zugewiesen, dessen Dimension sich ständig über die Zählvariable n<\/b> erweitert, wobei die ReDim<\/b>-Anweisung den Inhalt nicht zerstört, weil sie eine Preserve<\/b>-Klausel enthält. Optional können Sie der Prozedur per Parameter ein Limit<\/b> übergeben, welches die Anzahl der Elemente des Ergebnis-Arrays begrenzt. Ohne Limit kommt es zu etwa 9.000 Elementen.<\/p>\n
Sie rufen diese Funktion etwa so auf:<\/p>\n
Dim <\/span>arr() As String<\/span>\r\narr = CreateStringArray()\r\n... (Sortieren von arr() ) ...<\/pre>\n
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.<\/p>\n
Wizhook<\/h2>\n
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<\/b> ein, so finden Sie die Klasse Wizhook<\/b> 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:<\/p>\n
  Wizhook Is Nothing\r\n-> Falsch<\/pre>\n
Eine Methode der Klasse lautet SortStringArray<\/b> mit dieser Definition:<\/p>\n
Sub <\/span>SortStringArray(Array() As String<\/span>)<\/pre>\n
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<\/b>-Objekts. Sie schalten sie erst über das Setzen der Key<\/b>-Eigenschaft frei. Wozu Microsoft das implementiert hat, ist ein Rätsel, denn dieser Zahlenschlüssel ist natürlich keineswegs geheim:<\/p>\n
Sub <\/span>SortWizHook(sarr() As String<\/span>)\r\n     WizHook.Key = 51488399\r\n     WizHook.SortStringArray sarr\r\nEnd Sub<\/span><\/pre>\n
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.<\/p>\n
Der Key wird hier bei jedem Aufruf der Funktion SortWizHook<\/b> 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:<\/p>\n
Dim <\/span>arr() As String<\/span>\r\nDim <\/span>i As Long<\/span>\r\narr = CreateStringArray()\r\nSortWizHook arr\r\nFor i = 0 To Ubound(arr)\r\n     Debug.Print<\/span> arr(i)\r\nNext<\/span> i<\/pre>\n
Im VBA-Direktfenster listen sich nun alle Namen des Arrays alphanumerisch aufsteigend auf. Der Wizhook<\/b>-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:<\/p>\n
Sub <\/span>SortReverse (arr() As String<\/span>)\r\n     Dim <\/span>arrRet() As String<\/span>\r\n     Dim <\/span>n As Long<\/span>, i As Long<\/span>\r\n     \r\n     n= UBound<\/span>(arr)\r\n     Redim arrRet(n)\r\n     For i = 0 To n\r\n         arrRet(i) = arr(n-i)\r\n     Next<\/span> i\r\nEnd Sub<\/span><\/pre>\n
Das tut der Performance keinen Abbruch und verläuft ziemlich schnell.<\/p>\n
BubbleSort<\/h2>\n
Der Vollständigkeit halber bilden wir den BubbleSort<\/b>-Algorithmus nochmals in Listing 2 ab. Jedes Element des Arrays sarr<\/b> 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<\/b>. Eine absteigende Sortierung erhalten Sie hier durch Änderung der Vergleichszeile:<\/p>\n
Sub <\/span>BubbleSortStrings(sarr() As String<\/span>)\r\n     Dim <\/span>S As String<\/span>\r\n     Dim <\/span>i As Long<\/span>, j As Long<\/span>, n As Long<\/span>\r\n     \r\n     n = UBound<\/span>(sarr)\r\n     For i = 0 To n - 1\r\n         For j = i + 1 To n\r\n             If <\/span>sarr(i) > sarr(j) Then<\/span>\r\n                 S = sarr(i)\r\n                 sarr(i) = sarr(j)\r\n                 sarr(j) = S\r\n             End If<\/span>\r\n         Next<\/span> j\r\n     Next<\/span> i\r\nEnd Sub<\/span><\/pre>\n
Listing 2: Funktion zum Sortieren über BubbleSort<\/p>\n
If <\/span>sarr(i) < sarr(j) Then<\/span><\/pre>\n
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<\/b>-Methode erreichte dasselbe Ergebnis in nur 0,03 Sekunden!<\/p>\n
Sehen wir, ob sich dieser Wert durch andere Methoden noch unterbieten lässt.<\/p>\n
QuickSort<\/h2>\n
Dieser Algorithmus ist zweifellos der verbreitetste überhaupt. Es ist davon auszugehen, dass auch die Wizhook<\/b>-Methode, wie auch die Database Engine<\/b>, 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!<\/p>\n
Der Algorithmus in Listing 3 arbeitet rekursiv<\/b>. 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<\/b> und LL<\/b>, stellvertretend für Rechter Zeiger<\/b> und Linker Zeiger<\/b>.<\/p>\n
Public Sub <\/span>QuickSortStrings(sarr() As String<\/span>, Optional<\/span> ByVal LL As Long<\/span>, Optional<\/span> ByVal LR As Long<\/span>)\r\n     Dim <\/span>n1 As Long<\/span>, n2 As Long<\/span>\r\n     Dim <\/span>sTmp As String<\/span>, sSwap As String<\/span>\r\n     If <\/span>LR = 0 Then<\/span>   LL = LBound<\/span>(sarr): LR = UBound<\/span>(sarr)\r\n     n1 = LL: n2 = LR\r\n     sTmp = sarr((LL + LR) \\ 2)\r\n     Do\r\n         Do While<\/span> (sarr(n1) < sTmp) And (n1 < LR)\r\n             n1 = n1 + 1\r\n         Loop<\/span>\r\n         Do While<\/span> (sTmp < sarr(n2)) And (n2 > LL)\r\n             n2 = n2 - 1\r\n         Loop<\/span>\r\n         If <\/span>n1 <= n2 Then<\/span>\r\n             sSwap = sarr(n1)\r\n             sarr(n1) = sarr(n2)\r\n             sarr(n2) = sSwap\r\n             n1 = n1 + 1\r\n             n2 = n2 - 1\r\n         End If<\/span>\r\n     Loop<\/span> Until n1 > n2\r\n     If <\/span>LL < n2 Then<\/span> QuickSortStrings sarr, LL, n2\r\n     If <\/span>n1 < LR Then<\/span> QuickSortStrings sarr, n1, LR\r\nEnd Sub<\/span><\/pre>\n
Listing 3: Funktion zum Sortieren über Quicksort<\/p>\n
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.<\/p>\n
Sie übergeben der Funktion nur das Array und lassen die beiden optionalen Parameter unberücksichtigt:<\/p>\n
Dim <\/span>arr() As String<\/span>\r\narr = CreateStringArray()\r\nQuickSortStrings arr<\/pre>\n
Möchten Sie weiterlesen? Dann lösen Sie Ihr Ticket!<\/span>
\nHier geht es zur Bestellung des Jahresabonnements des Magazins Access [basics]<\/strong>:<\/span>
\nZur Bestellung ...<\/a><\/span>
\nDanach greifen Sie sofort auf alle rund 400 Artikel<\/strong> unseres Angebots zu - auch auf diesen hier!<\/span>
\nOder haben Sie bereits Zugangsdaten? Dann loggen Sie sich gleich hier ein:<\/span><\/p>\n<\/div>\n\n\t\n\t
\n\n\t\t\n\t\t