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.
Bitte beachten Sie: Zu diesem Tipp & Trick ist ein Update verfügbar. Bitte klicken Sie hier, um auf das Update zuzugreifen.
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.
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
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:
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
Möchten Sie mehr über dieses Thema erfahren oder haben weitere Fragen? Bitte kontaktieren Sie uns.
Arbeiten mit externen Excel-Arbeitsmappen Neben dem Zugriff auf die in INOSIM eingebaute Excel-Arbeitsmappe (siehe Tipp Nutzen Sie Ihr Excel-VBA-Wissen bei der Arbeit mit INOSIM), kann mit Hilfe…
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…
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…
Sie sehen gerade einen Platzhalterinhalt von Facebook. Um auf den eigentlichen Inhalt zuzugreifen, klicken Sie auf die Schaltfläche unten. Bitte beachten Sie, dass dabei Daten an Drittanbieter weitergegeben werden.
Mehr InformationenSie müssen den Inhalt von hCaptcha laden, um das Formular abzuschicken. Bitte beachten Sie, dass dabei Daten mit Drittanbietern ausgetauscht werden.
Mehr InformationenSie sehen gerade einen Platzhalterinhalt von Instagram. Um auf den eigentlichen Inhalt zuzugreifen, klicken Sie auf die Schaltfläche unten. Bitte beachten Sie, dass dabei Daten an Drittanbieter weitergegeben werden.
Mehr InformationenSie müssen den Inhalt von hCaptcha laden, um das Formular abzuschicken. Bitte beachten Sie, dass dabei Daten mit Drittanbietern ausgetauscht werden.
Mehr InformationenSie müssen den Inhalt von reCAPTCHA laden, um das Formular abzuschicken. Bitte beachten Sie, dass dabei Daten mit Drittanbietern ausgetauscht werden.
Mehr InformationenSie sehen gerade einen Platzhalterinhalt von Turnstile. Um auf den eigentlichen Inhalt zuzugreifen, klicken Sie auf die Schaltfläche unten. Bitte beachten Sie, dass dabei Daten an Drittanbieter weitergegeben werden.
Mehr InformationenSie sehen gerade einen Platzhalterinhalt von X. Um auf den eigentlichen Inhalt zuzugreifen, klicken Sie auf die Schaltfläche unten. Bitte beachten Sie, dass dabei Daten an Drittanbieter weitergegeben werden.
Mehr Informationen