26. November 2020

Schnelle Sortierung von Arrays

Bei der Sortierung von Arrays 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.

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.

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 As Variant, 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 As Variant
  Dim vSwap As Variant
  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
      Wend
      While (P < vArray(j) And j > firstRow)
        j = j - 1
      Wend
      If (i <= j) Then
        vSwap = vArray(i)
        vArray(i) = vArray(j)
        vArray(j) = vSwap
        i = i + 1
        j = j - 1
      End If
    Wend

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

Ein 2-dimensionales 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 As Variant, _
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 As Variant
  Dim P As Variant

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

  firstCol = LBound(vArray, 2)
  lastCol = UBound(vArray, 2)
  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
      Wend
      While (vArray(j, lColumn) > P) And j > firstRow
        j-=1
      Wend
    Else
      ' sort order descending
      While (vArray(i, lColumn) > P) And i < lastRow
        i+=1
      Wend
      While (vArray(j, lColumn) < P) And j > firstRow
        j-=1
      Wend
    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

Downloads

  • PDF-Ausdruck zu diesem Tipp & Trick

Fragen?

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

Array ( [posts_per_page] => 3 [post_type] => [category__in] => Array ( [0] => 171 ) [orderby] => rand [order] => ASC )

Mehr Tipps & Tricks

Erfahrenen Anwendenden von INOSIM ist bewusst, dass sie mit einer ereignisdiskreten Simulationssoftware arbeiten. Für die meisten dieser Ereignisse können VBA-Steuerungen aufgerufen werden, um das Simulationsverhalten…

In INOSIM kann die Verfügbarkeit von Ressourcen und Equipment mithilfe von Schichtkalendern ausgedrückt werden. Ein Schichtkalender legt fest, wann ein Equipment verfügbar ist oder wie…

Intervall-Auswertung des Transfer-Reports In diesem Tipp stellen wir Ihnen vor, wie Sie aus den von INOSIM erzeugten Reports automatisiert per VBA weitere Daten berechnen, um…

mehr

INOSIM Kontakt

Zu den lokalen Geschäftszeiten

Deutschland +49 231 97 00 250

USA +1 214 663 3101

Indien +91 9766 331 092