Button Home/Top/Zurück


Array Sortieren




Immer dann, wenn Daten nicht aus einer Tabelle oder Abfrage entnommen werden können, steht man vor dem Problem wo man diese zwischenspeichert und wie man dann sortiert.
Für die Zwischenspeicherung bietet sich ein dynamisches Array an.
Für die Sortierung verschiedene Sortieralgorithmen.

Der bekannteste und schnellste Sortieralgorithmus ist der rekursive QuickSort.
Wem die Rekursion ein Dorn im Auge ist, der sollte den BubbleSort verwenden.
Am besten ist allerdings die Sortierung beim Hineinschreiben der Werte in ein Array.

Beim QuickSort läuft in drei Schritten ab.
  • Teilen des Arrays
  • Tauschen von fehlplatzierten Elementen
  • Rekursiver Aufruf mit einen Teil-Array
Um das Array zu teilen wird einfach die Mitte des Arrays bestimmt.


Dabei wird die Formel Mitte = (Min. Element + Max. Element) / 2 angewendet. In diesem Beispiel also (0 + 7) / 2 = 3,5 » 3

Das Tauschen der fehlplatzierten Elemente bedeutet, das alle Elemente deren Wert kleiner als der Wert im mittleren Element sind nach rechts und alle Elemente deren Wert größer als der mittlere Wert nach links geschafft werden müssen.
Sinnigerweise werden hierbei immer zwei Elemente (eines das kleiner ist und eines das größer ist) vertauscht.

Der Wert des Elementes 1 ist 7 und damit größer als der Wert des mittleren Elementes 3.
Der Wert des Elementes 7 ist 3 und damit nicht größer als der Wert des mittleren Elementes.


Schritt 1


Die beiden Elemente werden vertauscht.


Schritt 2


Wichtig ist, das nach dem Vertauschen die Prüfung dort fortgesetzt wird, wo sie vorher beendet wurde.
Im Beispiel heißt dies, die Prüfung der linken Seite geht bei Element 2 weiter (in Element 1 wurde zuvor ein Größeres als das mittlere Element gefunden), die Prüfung der rechten Seite geht bei Element 6 weiter (in Element 7 wurde zuvor ein kleineres als das mittlere Element gefunden).
Hierbei wird auch deutlich, das die Prüfung der linken Seite von Links zur Mitte hin erfolgt, während die Prüfung der rechten Seite von Rechts zur Mitte hin erfolgt.

Als nächstes würden die Elemente 2 und 4 gefunden ...


Schritt 3


... und vertauscht werden.


Schritt 4


Nun könnte ein Skeptiker meinen, daß der Algorithmus nur bei diesem Beispiel funktioniert, da auf der Linken und Rechten Seite gleich viele Elemente vertauscht werden können/müssen.
Sollte ein Vertauschen zwischen kleiner Mitte und größer Mitte nicht möglich sein, dann wird mit dem Wert des mittleren Elementes vertauscht (siehe auch weitere Schritte).

Da die weitere Prüfung der beiden Seiten keine weiteren Unstimmigkeiten ergeben hat, kann nun der rekursive Aufruf für die Teil-Arrays (linker und rechter Teil) erfolgen.
Die Verarbeitung wird im realen Leben nacheinander erfolgen. In dieser Beschreibung erfolgt die Verarbeitung parallel, um ein wenig flotter voran zu kommen

Alles von vorne. D.h. als erstes die Mitte bestimmen...


Schritt 5


... dann Unstimmigkeiten suchen ...


Schritt 6


... dann Vertauschen.


Schritt 7


Ein Teil-Array kann als sortiert angesehen werden, wenn keine Teil-Arrays mehr gebildet werden können.
Anderenfalls heißt es weiter: Rekursiver Aufruf mit Teil-Array, Mitte bestimmen ...


Schritt 8

... Unstimmigkeiten suchen ...


Schritt 9

... Vertauschen ...


Schritt 10

... bis keine Teil-Arrays mehr gebildet werden können.


Schritt 11


Nachfolgend die VBA-Prozedur zum sortieren:
Nach einem Hinweis von Dr. Quicksort via Gästebucheintrag funktioniert der Quicksort nun auch korrekt.
Sub QuickSort(ByRef sArray As Variant, ByVal MinElem As Long, MaxElem As Long)  
'  
' QuickSort()  
'  
' Sortieren eines Arrays mit dem QuickSort-Algorithmus, dem wohl schnellsten  
' Sortieralgorithmus von Welt.  
'  
' IN:   sArray      Array das sortiert werden soll  
'       MinElem     erstes Element des Arrays (oder Teil-Arrays)  
'       MaxElem     letztes Element des Arrays (oder Teil-Arrays)  
'  
Dim Mitte As Long   
Dim vDummy As Variant   
Dim vMitte As Variant   
Dim i As Long, j As Long   
    '  
    ' Abbruchbedingung der Rekursion prüfen  
    '  
    If MinElem > MaxElem Then   
        '  
        ' Rekursion beenden  
        '  
        Exit Sub  
    End If   
    '  
    ' Ermittlung der Mitte des Arrays  
    '  
    Mitte = (MinElem + MaxElem) \ 2   
    vMitte = sArray(Mitte)   
    '  
    ' Für die Prüfung der linken und rechten  
    ' Seite die Zähler initialisieren  
    '  
    i = MinElem   
    j = MaxElem   
    Do   
        '  
        ' Von links bis zur Mitte prüfen  
        '  
        Do While sArray(i) < vMitte   
            i = i + 1   
        Loop   
        '  
        ' Von rechts bis zur Mitte prüfen  
        '  
        Do While sArray(j) > vMitte   
            j = j - 1   
        Loop   
           
        If i <= j Then   
            '  
            ' Die beiden gefundenen, falsch einsortierten  
            ' Elemente vertauschen  
            '  
            vDummy = sArray(j)   
            sArray(j) = sArray(i)   
            sArray(i) = vDummy   
            '  
            ' Prüfung bei der nächsten Position fortsetzen  
            '  
            i = i + 1   
            j = j - 1   
        End If   
           
    Loop Until i > j   
    '  
    ' Rekursiver Aufruf mit den Teil-Arrays  
    '  
    QuickSort sArray, MinElem, j   
    QuickSort sArray, i, MaxElem   
End Sub  

Modul Icon Modul als Textfile zum downloaden.
Im Gegensatz zum QuickSort ist der BubbleSort nicht rekursiv, allerdings auch nicht so schnell.
Beim BubbleSort wird jedes Element eines Arrays mit jedem anderen Element verglichen und ggf. vertauscht. Dabei wandern die kleinen Werte von rechts nach links, was (wenn man sich das Array hochkant vorstellt) so aussieht als ob Luftblasen in einem Wasserglas aufsteigen. Daher kommt auch der Name BubbleSort.

Der Algorithmus ist denkbar einfach.
Es wird mit dem Element 0 begonnen und dessen Wert mit dem Wert des nachfolgenden Elements verglichen. Wenn der Wert des Nachfolgers kleiner als der Wert des aktuellen Elementes ist, dann werden die beiden Werte vertauscht. Anschließend wird der Nachfolger zum aktuellen Element.

Es wird also im
  • 1. Schritt Element 0 mit Element 1 verglichen
  • 2. Schritt Element 1 mit Element 2 verglichen
  • 3. Schritt Element 2 mit Element 3 verglichen
  • 4. Schritt Element 3 mit Element 4 verglichen
  • 5. Schritt Element 4 mit Element 5 verglichen
  • 6. Schritt Element 5 mit Element 6 verglichen
  • 7. Schritt Element 6 mit Element 7 verglichen
Im unten dargestellten Schritt 8 werden lediglich die Werte getauscht.

Schritt 1

Schritt 2

Schritt 3

Schritt 4


Schritt 5

Schritt 6

Schritt 7

Schritt 8


Bei dieser Vorgehensart wird der höchste Wert im Array beim ersten Durchlauf in das letzte Element des Arrays eingetragen. Für den Algorithmus heißt dies, das die Prüfung beim zweiten Durchlauf nur bis zum vorletzten Element des Arrays erfolgen muß.
Nachfolgend die VBA-Prozedur zum sortieren:
Sub BubbleSort(ByRef sArray As Variant)
'
' BubbleSort()
'
' Sortieren eines Arrays mit dem BubbleSort-Algorithmus
'
' IN:   sArray  das zu sortierende Array
'
Dim j As Long              ' Zähler
Dim i As Long              ' noch ein Zähler
Dim vDummy As Variant      ' Dummy für Dreiecks-Tausch
    '
    ' Schleife über alle Elemente des Arrays
    '
    For j = UBound(sArray) - 1 To LBound(sArray) Step -1
        '
        ' Schleife vom Anfang des Arrays bis zum (n - j)'ten
        ' Element des Arrays
        '
        For i = LBound(sArray) To j
            '
            ' Prüfen, ob der Nachfolger kleiner als das
            ' aktuelle Element ist
            '
            If sArray(i) > sArray(i + 1) Then
                '
                ' Werte der Elemente vertauschen
                '
                vDummy = sArray(i)
                sArray(i) = sArray(i + 1)
                sArray(i + 1) = vDummy
            End If
        Next i
    Next j
End Sub

Modul Icon Modul als Textfile zum downloaden.

Am besten ist es natürlich, wenn man beim Eintragen von Werten in ein Array gleich dafür sorgt, daß diese in der richtigen Reihenfolge abgelegt werden.
Dazu dient folgende Prozedur.
Sub InsertValue(NewVal As String, ByRef sArray As Variant)
'
' InsertValue()
'
' Fügt einen String in ein String-Array ein.
' Dabei wird auf die Sortierung des Array geachtet.
'
' IN:   NewVal      String der in das Array eingefügt werden soll
'       sArray    Array das erweitert werden soll
'
' OUT:  None
'
Dim MaxIdx As Long  ' Größe des Arrays
Dim i As Integer    ' Zähler
Dim j As Integer    ' noch ein Zähler
    '
    ' Array um eines Speicherplatz erweitern
    '
    MaxIdx = UBound(sArray)
    ReDim Preserve sArray(MaxIdx + 1)
    '
    ' Schleife über alle Einträge des Arrays
    '
    i = LBound(sArray)
    While i < MaxIdx
        '
        ' den ersten Eintrag im Array suchen,
        ' der größer als der neue Wert ist
        '
        If sArray(i) > NewVal Then
            '
            ' alle nachfolgenden Einträge des Arrays
            ' um einen Platz nach hinten verschieben
            '
            For j = MaxIdx - 1 To i Step -1
                sArray(j + 1) = sArray(j)
            Next j
            '
            ' neuen Wert in Array eintragen
            '
            sArray(i) = NewVal
 
            Exit Sub
 
        End If
        i = i + 1
    Wend
    '
    ' es wurde kein größer Eintrag im Array gefunden,
    ' darum den neuen Wert ans Ende stellen
    sArray(i) = NewVal
 
End Sub


Modul Icon Modul als Textfile zum downloaden.

Button Home/Top/Zurück