Arrays sortieren mit BubbleSort und QuickSort

Veröffentlicht: 01. Mrz 2002 | Aktualisiert: 17. Jun 2004

Von Mathias Schiffer

Für das interne Sortieren von Feldern gibt es in der Informatik diverse Algorithmen, von denen "BubbleSort" und "QuickSort" die wohl bekanntesten Vertreter darstellen.

BubbleSort

Der BubbleSort-Algorithmus zeichnet sich durch ein einfaches Funktionsprinzip und entsprechend einfache Implementation aus – er eignet sich jedoch vornehmlich für kleine Felder, da seine Laufzeit mit der Anzahl zu sortierender Elemente quadratisch ansteigt.

Zur Sortierung wird die Menge der zu sortierenden Elementen mittels einer Indexvariablen j von rechts nach links durchlaufen, wobei mit dem zweiten Element von rechts begonnen wird. Für jedes so ermittelte Element wird mit Hilfe einer Indexvariablen i die Menge der links davon liegenden Elemente durchlaufen, wobei jedes dieser Elemente mit seinem Nachfolger verglichen wird. Sind Element und Nachfolger falsch sortiert, werden sie gegeneinander ausgetauscht:

  For j = UBound(ArrayToSort) - 1 To LBound(ArrayToSort) Step -1 
    ' Alle links davon liegenden Zeichen auf richtige Sortierung 
    ' der jeweiligen Nachfolger überprüfen: 
    For i = LBound(ArrayToSort) To j 
      ' Ist das aktuelle Element seinem Nachfolger gegenüber korrekt sortiert? 
      If ArrayToSort(i) > ArrayToSort(i + 1) Then 
        ' Element und seinen Nachfolger vertauschen. 
        vTemp = ArrayToSort(i) 
        ArrayToSort(i) = ArrayToSort(i + 1) 
        ArrayToSort(i + 1) = vTemp 
      End If 
    Next i 
  Next j

QuickSort

Der QuickSort-Algorithmus verwendet ein weniger einfaches Sortierungsverfahren, ist jedoch allgemein das schnellste bekannte interne Sortierverfahren, das seine Vorzüge gegenüber dem BubbleSort schon bei einer vergleichsweise geringen Anzahl an Elementen (etwa 20) ausspielen kann.

Das QuickSort-Verfahren teilt das Feld zu sortierender Elemente in zwei möglichst gleich große Teilfelder auf, indem ein Mittenelement ausgewählt wird. Mit einem Index i wird dann das linke Teilfeld von links nach rechts durchlaufen, bis ein Element gefunden wird, das gegenüber dem ausgewählten Mittenelement falsch sortiert ist. Analog wird das rechte Teilfeld von rechts nach links mit einem zweiten Index j durchlaufen, bis ein falsch sortiertes Element gefunden wird. Werden in beiden Teilfeldern falsch einsortierte Elemente gefunden, werden diese gegeneinander ausgetauscht und die Suche nach weiteren, gegenüber dem Mittenelement falsch sortierten Elementen fortgeführt. Haben sich die Indizes bei der Suche überschnitten, werden die beiden ausgewählten Teilfelder auf die gleiche Weise rekursiv geordnet:

Private Sub QuickSort( _ 
                      ByRef ArrayToSort As Variant, _ 
                      ByVal Low As Long, _ 
                      ByVal High As Long) 
Dim vPartition As Variant, vTemp As Variant 
Dim i As Long, j As Long 
  If Low > High Then Exit Sub  ' Rekursions-Abbruchbedingung 
  ' Ermittlung des Mittenelements zur Aufteilung in zwei Teilfelder: 
  vPartition = ArrayToSort((Low + High) \ 2) 
  ' Indizes i und j initial auf die äußeren Grenzen des Feldes setzen: 
  i = Low: j = High 
  Do 
    ' Von links nach rechts das linke Teilfeld durchsuchen: 
    Do While ArrayToSort(i) < vPartition 
      i = i + 1 
    Loop 
    ' Von rechts nach links das rechte Teilfeld durchsuchen: 
    Do While ArrayToSort(j) > vPartition 
      j = j - 1 
    Loop 
    If i <= j Then 
      ' Die beiden gefundenen, falsch einsortierten Elemente 
austauschen: 
      vTemp = ArrayToSort(j) 
      ArrayToSort(j) = ArrayToSort(i) 
      ArrayToSort(i) = vTemp 
      i = i + 1 
      j = j - 1 
    End If 
  Loop Until i > j  ' Überschneidung der Indizes 
  ' Rekursive Sortierung der ausgewählten Teilfelder. Um die 
  ' Rekursionstiefe zu optimieren, wird (sofern die Teilfelder 
  ' nicht identisch groß sind) zuerst das kleinere 
  ' Teilfeld rekursiv sortiert. 
  If (j - Low) < (High - i) Then 
    QuickSort ArrayToSort, Low, j 
    QuickSort ArrayToSort, i, High 
  Elsea 
    QuickSort ArrayToSort, i, High 
    QuickSort ArrayToSort, Low, j 
  End If 
End Sub