Schnelle Sortierung von Arrays und Tabellen

Bei der Sortierung von Arrays und Tables kann die Laufzeit des angewendeten Sortierverfahrens eine entscheidende Rolle spielen. Bei kleineren Datenmengen mag diese noch nicht sehr stark ins Gewicht fallen, so dass auch einfach zu implementierende Verfahren wie Bubblesort noch akzeptabel sind. Bei großen Datenmengen verbieten diese sich allerdings von selbst. Im Folgenden wird mit Quicksort ein Verfahren vorgestellt, welches zu den schnellsten Sortiermethoden gehört und auch für große Datenmengen geeignet ist. In diesem Tipp & Trick wurde dieser Algorithmus für Arrays und Tables in WWB.NET implementiert und ein Beispielmodell mit Testdaten bereitgestellt.

Teile und herrsche

Der Sortier-Algorithmus arbeitet nach dem Teile und Herrsche-Prinzip. Dabei wird zunächst ein Element, vorzugsweise in der Mitte des gesamten Bereiches, ausgesucht (das sogenannte Pivot-Element) und so der Bereich in zwei Teilbereiche geteilt. Alle Elemente, die kleiner sind als das ausgesuchte Pivot-Element, kommen in den ersten Bereich, alle, die größer sind, in den zweiten Bereich. Elemente, die gleich groß sind, verbleiben, wo sie sind.

Abbildung1: Funktionsprinzip des Quicksort-Algorithmus

Anschließend wird jeder der Teilbereiche wieder nach dem gleichen Verfahren behandelt. D. h., es werden in jedem Teilbereich Unterteilbereiche erzeugt, in denen die Elemente wieder nach Größe aufgeteilt werden. Dieses Verfahren wird fortgesetzt, bis es nur noch Teilbereiche der Länge 1 gibt (Rekursion).

Ein weiterer Vorteil dieses Verfahrens ist neben der hohen Geschwindigkeit der Umstand, dass kein zusätzlicher Speicherplatz benötigt wird, da die einzelnen Elemente nur innerhalb des Bereiches vertauscht werden.

Eine Liste sortieren

Das erste hier gezeigte Code-Beispiel kann zur Sortierung einer einfachen Liste (eindimensionales Array) verwendet werden. Dazu werden der Routine das Array und die Indizes der ersten und letzten Zeile des zu sortierenden Bereichs übergeben. Durch die Angabe dieser Indizes ist es möglich, nur einen bestimmten Bereich einer Liste zu sortieren. Nach der Ausführung der Routine liegen die Elemente in aufsteigender Reihenfolge in der Liste vor.

Public Sub Quicksort (vArray, firstRow As Long, lastRow As Long)
  '------------------------------------------------------------------------
  ' Sorts a one-dimensional VBA array from smallest to largest
  ' Input: vArray array 1dim array, containing the data to be sorted
  ' firstRow long first line of the area to be sorted
  ' lastRow long last line of the area to be sorted
  '------------------------------------------------------------------------
  Dim i As Long
  Dim j As Long
  Dim P
  Dim vSwap
  If lastRow >= 0 Then
    i = firstRow
    j = lastRow
    P = vArray((firstRow + lastRow) \ 2) ' Pivot element
    While (i <= j)
      While (vArray(i) < P And i < lastRow)
        i = i + 1
      End While
      While (P < vArray(j) And j > firstRow)
        j = j - 1
      End While
      If (i <= j) Then
        vSwap = vArray(i)
        vArray(i) = vArray(j)
        vArray(j) = vSwap
        i = i + 1
        j = j - 1
      End If
    End While

    ' recursion
    If (firstRow < j) Then Quicksort (vArray, firstRow, j)
    If (i < lastRow) Then Quicksort (vArray, i, lastRow)
  End If
End Sub

Beispielsweise kann die Liste List (als eindimensionales Array) komplett sortiert werden:

Call Quicksort(List, LBound(List), UBound(List))

Ein zweidimensionales Array sortieren

Das zweite hier gezeigte Code-Beispiel arbeitet nach dem gleichen Verfahren, allerdings werden hier zweidimensionale Arrays sortiert. Neben dem zu sortierenden Array werden der Routine noch folgende Parameter übergeben:

Parameter lColumn: Gibt an, welche Spalte sortiert werden soll.
Parameter lSortOrder: Sortierreihenfolge (auf- oder absteigend).
Parameter firstRow: Index der ersten Zeile des zu sortierenden Bereichs (s. o.).
Parameter lastRow: Index der letzten Zeile des zu sortierenden Bereichs (s. o.).

Public Sub Quicksort2Dim (vArray , _
Optional ByVal lColumn As Long = 0, _
Optional lSortOrder As Long = 1, _
Optional ByVal firstRow As Long = -1, _
Optional ByVal lastRow As Long = -1)
  '------------------------------------------------------------------------
  ' Sorts a 2-dimensional array according to the specified sort order
  ' Input: vArray array 2dim array, containing the data to be sorted
  ' lColumn long column, which is to be sorted (optional)
  ' lSortOrder long Sort order, 0 = descending, 1 = ascending) (optional)
  ' firstRow long first line of the area to be sorted (optional)
  ' lastRow long last line of the area to be sorted (optional)
  '------------------------------------------------------------------------

  Dim i As Long
  Dim j As Long
  Dim u As Long
  Dim firstCol As Integer
  Dim lastCol As Integer
  Dim h
  Dim P

  If firstRow = -1 Then firstRow = LBound(vArray)
  If lastRow = -1 Then lastRow = UBound(vArray) 'vArray.RowCount '

  firstCol = LBound(vArray, 2)  '1 '
  lastCol = UBound(vArray, 2)   'vArray.ColumnCount '
  i = firstRow
  j = lastRow
  P = vArray((firstRow + lastRow) / 2, lColumn)

  Do
    If lSortOrder = 1 Then
      ' sort order ascending
      While (vArray(i, lColumn) < P) And i < lastRow
        i+=1
      End While
      While (vArray(j, lColumn) > P) And j > firstRow
        j-=1
      End While
    Else
      ' sort order descending
      While (vArray(i, lColumn) > P) And i < lastRow
        i+=1
      End While
      While (vArray(j, lColumn) < P) And j > firstRow
        j-=1
      End While
    End If

    If (i <= j) Then
      For u = firstCol To lastCol
        h = vArray(i, u)
        vArray(i, u) = vArray(j, u)
        vArray(j, u) = h
      Next u
      i += 1
      j -= 1
    End If
  Loop Until (i > j)

  ' recursion
  If (firstRow < j) Then Quicksort2Dim (vArray, lColumn, lSortOrder, firstRow, j)
  If (i < lastRow) Then Quicksort2Dim (vArray, lColumn, lSortOrder, i, lastRow)
End Sub

Soll also zum Beispiel TwoDim nach der zweiten Spalte in aufsteigender Reihenfolge sortiert werden, kann der folgende Aufruf ausgeführt werden:

Call Quicksort2Dim(TwoDim, 1, 1, -1, -1)

Hier ist der Parameter lColumn=1, da der Spaltenindex des Arrays bei 0 beginnt.

Eine Tabelle sortieren

Das dritte hier gezeigte Code-Beispiel arbeitet auch nach dem gleichen Verfahren, allerdings werden hier Tabelleneinträge sortiert. Neben der zu sortierenden Tabelle werden der Routine die gleichen Parameter übergeben wie im vorherigen Beispiel.

Public Sub QuicksortTable (vTable As Table, _
    Optional ByVal lColumn As Long = 1, _
    Optional lSortOrder As Long = 1, _
    Optional ByVal firstRow As Long = 1, _
    Optional ByVal lastRow As Long = -1)
    '------------------------------------------------------------------------
    ' Sorts a table according to the specified sort order
    ' vTable table, containing the data to be sorted
    ' lColumn long column, which is to be sorted (optional)
    ' lSortOrder long Sort order, 0 = descending, 1 = ascending (optional)
    ' firstRow long first line of the area to be sorted (optional)
    ' lastRow long last line of the area to be sorted (optional)
    '------------------------------------------------------------------------
    
    Dim i, k As Long
    Dim j As Long
    Dim u As Long
    Dim firstCol As Integer
    Dim lastCol As Integer 
    Dim h_i , h_j 
    Dim P

    If lastRow = -1 Then lastRow = vTable.RowCount
    
    If vTable.ColumnIndex = True Then
        firstCol = 0
    Else
        firstCol = 1
    End If
    lastCol = vTable.ColumnCount
    i = firstRow
    j = lastRow
    k = Int((firstRow + lastRow) / 2)
    P = vTable( k, lColumn)
    
    Do
        If lSortOrder = 1 Then
            ' sort order ascending
            While (vTable(i, lColumn) < P) And i < lastRow
                i += 1
            End While
            While (vTable(j, lColumn) > P) And j > firstRow
                j -= 1
            End While
        Else
            ' sort order descending
            While (vTable(i, lColumn) > P) And i < lastRow
                i+=1
            End While
            While (vTable(j, lColumn) < P) And j > firstRow
                j-=1
            End While
        End If

        If (i <= j) Then
            
            For u = firstCol To lastCol
                h_i = vTable(i, u)              'save value i
                h_j = vTable(j, u)              'save value j
                vTable(j, u) = Nothing          'overwrite value j with nothing (necessary for index)
                vTable(i, u) = h_j              'overwrite i with j
                vTable(j, u) = h_i              'write i into j
            Next u
            i += 1
            j -= 1
        End If
    Loop Until (i > j)

    ' recursion
    If (firstRow < j) Then QuicksortTable (vTable, lColumn, lSortOrder, firstRow, j)
    If (i < lastRow) Then QuicksortTable (vTable, lColumn, lSortOrder, i, lastRow)

End Sub

So kann das Table-Objekt Tab beispielsweise nach den Einträgen in der ersten Spalte in absteigender Reihenfolge alphabetisch sortiert werden, durch die Ausführung von:

QuicksortTable(Tab, 1, 0, 1, -1)

Eine Tabelle alphabetisch sortieren

Zwar kann mit der Subroutine QuicksortTable auch Text sortiert werden, allerdings wird nach Groß- und Kleinschreibung unterschieden (bspw. ZZ vor aa). Mit dem hier gezeigten vierten Code-Beispiel lassen sich Tabelleneinträge alphabetisch sortieren, unabhängig von der Groß- und Kleinschreibung. Neben der zu sortierenden Tabelle werden der Routine die gleichen Parameter übergeben wie in den vorangegangenen beiden Beispielen, wobei die Einträge in der zu sortierenden Spalte (Parameter: lColumn) als String erfasst werden.

Public Sub QuicksortAlpha (vTable As Table, _
Optional ByVal lColumn As Long = 1, _
Optional lSortOrder As Long = 1, _
Optional ByVal firstRow As Long = 1, _
Optional ByVal lastRow As Long = -1)
  '------------------------------------------------------------------------
  ' Sorts a 2-dimensional array according to the specified sort order
  ' Input: vTable table, containing the data to be sorted
  ' lColumn long column, which is to be sorted (optional)
  ' lSortOrder long Sort order, 0 = descending, 1 = ascending) (optional)
  ' firstRow long first line of the area to be sorted (optional)
  ' lastRow long last line of the area to be sorted (optional)
  '------------------------------------------------------------------------

    Dim i, k As Long
    Dim j As Long
    Dim u As Long
    Dim firstCol As Integer
    Dim lastCol As Integer
    Dim h_i , h_j
    Dim P

    If lastRow = -1 Then lastRow = vTable.RowCount

    If vTable.ColumnIndex = True Then
        firstCol = 0
    Else
        firstCol = 1
    End If
  lastCol = vTable.ColumnCount
  i = firstRow
  j = lastRow
  k = Int((firstRow + lastRow) / 2)
  P = vTable( k, lColumn)

  Do
    If lSortOrder = 1 Then
      ' sort order ascending
      While (StrComp(vTable(i, lColumn), P, VbCompareMethod.vbTextCompare) < 0) And i < lastRow
        i+=1
      End While
      While (StrComp(vTable(j, lColumn), P, VbCompareMethod.vbTextCompare) > 0) And j > firstRow
        j-=1
      End While
    Else
      ' sort order descending
      While (StrComp(vTable(i, lColumn), P, VbCompareMethod.vbTextCompare) > 0) And i < lastRow
        i+=1
      End While
      While (StrComp(vTable(j, lColumn), P, VbCompareMethod.vbTextCompare) < 0) And j > firstRow
        j-=1
      End While
    End If

    If (i <= j) Then
        For u = firstCol To lastCol
            h_i = vTable(i, u)              'save value i
            h_j = vTable(j, u)              'save value j
            vTable(j, u) = Nothing          'overwrite value j with nothing (necessary for index)
            vTable(i, u) = h_j              'overwrite i with j
            vTable(j, u) = h_i              'write i into j
        Next u
        i += 1
        j -= 1
    End If
  Loop Until (i > j)

  ' recursion
  If (firstRow < j) Then QuicksortAlpha (vTable, lColumn, lSortOrder, firstRow, j)
  If (i < lastRow) Then QuicksortAlpha (vTable, lColumn, lSortOrder, i, lastRow)
End Sub

Soll zum Beispiel das Table-Objekt Tab alphabetisch nach den Textfeldern in Spalte 5 in aufsteigender Reihenfolge sortiert werden, kann der folgende Aufruf ausgeführt werden:

QuicksortAlpha(Tab, 5, 1, 1, -1)

Download

Ein Beispielmodell mit allen vier Subroutinen inklusive der benötigten Funktionen zum Lesen und Schreiben von Tabellen steht im Download-Bereich (siehe Schaltfläche unten) zur Verfügung.

Abbildung 2: Sortierbeispiel: Eine Tabelle mit mehreren Spalten (links) wurde alphabetisch nach den Einträgen in Spalte 5 sortiert (rechts)

Downloads

Fragen?

Möchten Sie mehr über dieses Thema erfahren oder haben weitere Fragen? Bitte kontaktieren Sie uns.

Mehr Tipps & Tricks

2. Mai 2022