Home > Artikel > Ausgabe 1/2016 > Bubble Sort

Bubble Sort

Achtung: Sie sind nicht angemeldet. Wenn Sie Abonnent sind und sich anmelden, lesen Sie den kompletten Artikel, laden das PDF herunter oder probieren die Beispieldatenbank aus (sofern vorhanden).

Solange Sie mit Datenzugriffsobjekten hantieren, ist das Sortieren von Daten eine einfache Angelegenheit. Diese übernehmen Sortierungen etwa über die SQL-Anweisung OrderBy oder dezidierte Sort-Methoden. Bei in Arrays untergebrachten Datenmengen unter VBA lässt Sie Access jedoch im Regen stehen. Hier kommen Sie um eigens programmierte Routinen nicht herum.

Beispieldatenbank

Die Beispiele dieses Artikels finden Sie in der Datenbank 1601_Klassenmodule.accdb im VBA-Modul mdlSort.

Abstract

Hin und wieder kommt es vor, dass Sie Daten nicht nur über Recordsets verwalten müssen, sondern auch über Arrays. Ein Beispiel wäre das Einlesen externer Textdateien, die tabellarischen Aufbau aufwiesen. In der Regel öffnen Sie solche Dateien über die Open-Anweisung und speichern ihren Inhalt in eine String-Variable. Die Split-Methode ermöglicht anschließend das Auftrennen der Zeilen in die Elemente eines String-Arrays. Möchten Sie diese Elemente nun nach einem bestimmten Kriterium sortieren, so ist eine Sortierroutine gefragt.

Es existiert ein Unmenge von Sortieralgorithmen mit Namen, wie QuickSort, HeapSort, MergeSort, ShellSort oder InsertionSort, die in der Regel zwar meist mit nur wenigen Zeilen Programmcode auskommen, jedoch häufig in ihrer Funktionalität nur schwer zu durchschauen sind. Anders beim BubbleSort-Algorithmus, der zwar in Hinsicht auf Performance der mit Abstand ineffizienteste ist, dafür jedoch umso leichter zu verstehen. Sollten Sie nicht Hunderttausende Elemente sortieren wollen, so spielt die Performance auf heutigen Rechnern in diesem Fall keine Rolle mehr.

BubbleSort

Die Sache ist recht simpel: Sie haben etwa ein eindimensionales Array mit allerlei Zeichenfolgen vor sich, die in aufsteigende Reihenfolge gebracht werden sollen. Dazu vergleicht BubbleSort jedes Element mit jedem und entscheidet, welches größer oder kleiner ist. Trifft dies zu, so vertauscht es die beiden, andernfalls nicht. Ein Beispiel-Listing sagt hier mehr, als viele Worte.

Listing 1 stellt die Routine SortArray vor, wie Sie sie im Modul mdlSort der Beispieldatenbank vorfinden. Sie übergeben der Prozedur ein Array mit Elementen, die keinesfalls nur vom Typ String sein müssen. Das Ganze funktioniert auch mit Zahlenwerten beliebiger Art, oder auch mit Datumswerten, da als Parameter MyArray ein Variant angegeben ist.

Public Enum eSortArray

     eSortAscending = 1

     eSortDescending = -1

End Enum

Sub SortArray(MyArray As Variant, Optional Order As eSortArray = eSortAscending)

     If IsEmpty(MyArray) Then Exit Sub

     

     Dim i As Long, j As Long

     Dim n As Long

     Dim tmp As Variant

     Dim ret As Boolean

     

     n = UBound(MyArray)

     For i = 0 To n - 1

         For j = i + 1 To n

             If Order = eSortAscending Then

                 ret = (MyArray(i) < MyArray(j))

             Else

                 ret = (MyArray(i) > MyArray(j))

             End If

             If ret = 0 Then

                 tmp = MyArray(i)

                 MyArray(i) = MyArray(j)

                 MyArray(j) = tmp

             End If

         Next j

     Next i

End Sub

Listing 1: Implementation des Bubble-Sort-Algorithmus in der Prozedur SortArray

Mit dem optionalen Parameter Order können Sie weiterhin spezifizieren, ob die Elemente auf- oder Absteigend sortiert werden sollen. Nach dem Durchlaufen der Routine ist das übergebene Array dann sortiert.

Damit Sie beim Aufruf der Prozedur mit IntelliSense beglückt werden, ist der Order-Parameter vom Enumerationstyp eSortArray. Diese Enumeration ist im Kopf des Moduls deklariert. In der Folge wird Ihnen beim Aufrufen für den zweiten Funktionsparameter gleich eine der beiden Möglichkeiten eSortAscending (aufsteigend) oder eSortDescending (absteigend) angeboten.

Die erste Zeile der Prozedur testet zunächst über die IsEmpty-Funktion, ob MyArray überhaupt einen Inhalt hat. Falls nicht, so wird die Prozedur schlicht verlassen. Mit UBound wird nun ermittelt, wie viele Elemente das Array enthält. Die Hilfsvariable n nimmt diesen Wert auf.

Und nun geht es in die zwei verschachtelten For-Next-Schleifen mit ihren Iteratoren i und j. Die Variable i zählt vom ersten bis zum vorletzten Element des Arrays, die Variable j hingegen beginnt mit eins größer, als i, und endet beim letzten Element. Auf diese Weise kommen alle denkbaren Kombinationen von Elementen zusammen. Die Probe auf's Exempel bei vier Elementen:

i - j:

1 - 2

1 - 3

1 - 4

2 - 3

2 - 4

3 - 4

Sie haben das Ende des frei verfügbaren Teil dieses Artikels erreicht!

Wenn Sie mehr lesen und auf viele weitere Artikel zugreifen möchten, melden Sie sich als Abonnent unter Login an. Falls nicht, bestellen Sie doch einfach ein Jahresabonnement!