Rubrik: Variablen/Strings · Algorithmen/Mathematik | VB-Versionen: VB4, VB5, VB6 | 06.11.01 |
QuickSort in VB Ein sehr schneller Sortier-Algorithmus zum Sortieren eines beliebigen (Teil-)Arrays für beliebige Datentypen. | ||
Autor: Dieter Otter | Bewertung: | Views: 72.278 |
www.tools4vb.de | System: Win9x, WinNT, Win2k, WinXP, Win7, Win8, Win10, Win11 | Beispielprojekt auf CD |
Bei dem QuickSort-Algorithmus handelt es sich (wie der Name schon sagt) um einen sehr schnellen Sortier-Algorithmus, der nicht einmal so sehr kompliziert ist. Der Algorithmus arbeitet rekursiv nach dem Divide-And-Conquer Prinzip, was soviel heisst, wie: "Teilen und Vergleichen".
Die sortierende Menge wird in zwei Teilstücke geteilt (Devide). Danach werden beiden Teilmengen rekursiv sortiert. Wieder zusammengesetzt ergeben beide Teilmengen die sortierte Gesamtmenge. Die Aufteilung erfolgt, indem zunächst ein Vergleichselement x gewählt wird. Alle Elemente der Folge, die kleiner als x sind, kommen in das erste Teilstück. Alle Elemente, die größer als x sind, kommen in das zweite Teilstück. Sobald ein Teilstück nur noch aus einem einzigen Element besteht, endet die Rekursion.
Und hier der Code für den QuickSort-Algorithmus
' QuickSort-Algorithmus ' ' vSort() : zu sortierendes Array ' lngStart, lngEnd: zu sortierender Bereich ' ========================================== Public Sub QuickSort(vSort As Variant, _ Optional ByVal lngStart As Variant, _ Optional ByVal lngEnd As Variant) ' Wird die Bereichsgrenze nicht angegeben, ' so wird das gesamte Array sortiert If IsMissing(lngStart) Then lngStart = LBound(vSort) If IsMissing(lngEnd) Then lngEnd = UBound(vSort) Dim i As Long Dim j As Long Dim h As Variant Dim x As Variant i = lngStart: j = lngEnd x = vSort((lngStart + lngEnd) / 2) ' Array aufteilen Do While (vSort(i) < x): i = i + 1: Wend While (vSort(j) > x): j = j - 1: Wend If (i <= j) Then ' Wertepaare miteinander tauschen h = vSort(i) vSort(i) = vSort(j) vSort(j) = h i = i + 1: j = j - 1 End If Loop Until (i > j) ' Rekursion (Funktion ruft sich selbst auf) If (lngStart < j) Then QuickSort vSort, lngStart, j If (i < lngEnd) Then QuickSort vSort, i, lngEnd End Sub
Um sich einmal ein Bild von der Geschwindigkeit des QuickSort-Verfahrens gegenüber z.B. dem BubbleSort-Verfahren machen zu können, haben wir ein Long-Array mit 10.000 Elementen sowohl mit QuickSort als auch mit BubbleSort sortieren lassen. Beides mal wurde die benötigte Zeit gemessen:
QuickSort: 140 Millisekunden
BubbleSort: 117.980 Millisekunden (= knapp 2 Minuten!)
Erstaunlich, nicht wahr?