vb@rchiv
VB Classic
VB.NET
ADO.NET
VBA
C#
sevDataGrid - Gönnen Sie Ihrem SQL-Kommando diesen krönenden Abschluß!  
 vb@rchiv Quick-Search: Suche startenErweiterte Suche starten   RSS-Feeds  | Newsletter  | Impressum  | Datenschutz  | vb@rchiv CD Vol.6  | Shop Copyright ©2000-2019
 
zurück
Rubrik: Variablen/Strings · Algorithmen/Mathematik   |   VB-Versionen: VB4, VB5, VB606.11.01
QuickSort in VB

Ein sehr schneller Sortier-Algorithmus zum Sortieren eines beliebigen (Teil-)Arrays für beliebige Datentypen.

Autor:   Dieter OtterBewertung:     [ Jetzt bewerten ]Views:  63.526 
www.tools4vb.deSystem:  Win9x, WinNT, Win2k, WinXP, Vista, Win7, Win8, Win10 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?
 

Dieser Tipp wurde bereits 63.526 mal aufgerufen.

Voriger Tipp   |   Zufälliger Tipp   |   Nächster Tipp

Über diesen Tipp im Forum diskutieren
Haben Sie Fragen oder Anregungen zu diesem Tipp, können Sie gerne mit anderen darüber in unserem Forum diskutieren.

Neue Diskussion eröffnen

nach obenzurück


Anzeige

Kauftipp Unser Dauerbrenner!Diesen und auch alle anderen Tipps & Tricks finden Sie auch auf unserer aktuellen vb@rchiv  Vol.6
(einschl. Beispielprojekt!)

Ein absolutes Muss - Geballtes Wissen aus mehr als 8 Jahren vb@rchiv!
- nahezu alle Tipps & Tricks und Workshops mit Beispielprojekten
- Symbol-Galerie mit mehr als 3.200 Icons im modernen Look
Weitere Infos - 4 Entwickler-Vollversionen (u.a. sevFTP für .NET), Online-Update-Funktion u.v.m.
 
   

Druckansicht Druckansicht Copyright ©2000-2019 vb@rchiv Dieter Otter
Alle Rechte vorbehalten.
Microsoft, Windows und Visual Basic sind entweder eingetragene Marken oder Marken der Microsoft Corporation in den USA und/oder anderen Ländern. Weitere auf dieser Homepage aufgeführten Produkt- und Firmennamen können geschützte Marken ihrer jeweiligen Inhaber sein.

Diese Seiten wurden optimiert für eine Bildschirmauflösung von mind. 1280x1024 Pixel