Eindimensionales Array sortieren

Eindimensionales Array mit QuickSort sortieren

In VBA gibt es keine Möglichkeit, ein Array mittels einer integrierten Funktion zu sortieren. Darum wird die Überzahl der Programmierer auf eine der beiden bekanntesten Sortiermethoden zurückgreifen: BubbleSort und QuickSort. Obwohl BubbleSort etwas leichter lesbar ist, kann ich die Methode nicht empfehlen; sie ist nur bis zu etwa 25 Einträgen in Sachen Geschwindigkeit dem QuickSort ebenbürtig oder überlegen.

In der hier vorgestellten Routine wird ein leeres Blatt mit 65.000 Zufallszahlen gefüllt und diese werden in der Nachbarspalte sortiert zurückgegeben. Den Code finden Sie in gepackter Form in dieser Datei als reine Textdatei und zum direkten Import in Tabelle1 als *.cls.

Prinzipiell können Sie den Code so verwenden, wie er ist. Kleine Anpassungen sind naturgemäß erforderlich, wenn ein anderer Bereich angesprochen werden soll. Darum ist auch einiges an Variablen mehr vorhanden, als bei einer festen Vorgabe oder wenn der Code für erfahrene Programmierer gedacht wäre.

Das oberste Modul SortierTest() dient ausschließlich dazu, dass Sie ein wenig die Geschwindigkeit einschätzen können. Die Begrenzung auf 65.500 Datensätze ist wegen älterer Excel-Versionen (bis Excel 2003) erforderlich, ab der 2007er-Version können Sie auch gerne 1 Millionen Zahlen erzeugen lassen. 🙂  Einige Hinweise zu diesen Zeilen:

lRow = 65500 + fRow – 1

wird Sie vielleicht etwas nachdenklich machen. So erreiche ich, dass exakt 65.500 Zeilen erzeugt werden. Die erste Zeile ist ja Zeile 2. Die 65.000 dazu addiert würde ja 65.002 als letzte Zeile des Bereichs ergeben. Darum muss noch 1 subtrahiert werden.

Dass dort anschließend per Funktion ZUFALLSBEREICH() erst eine Zufallszahl in A2 generiert wird, haben Sie gewiss erkannt. Per Ausfüllfunktion werden nun alle Zellen des Bereichs mit einer weiteren Zufallszahl beschrieben. Anschließend werden die Funktionswerte in feste Werte umgewandelt, damit sich beim Sortieren nichts mehr durch Neuberechnung ändern kann.

Der so gefüllte Bereich wird nun in ein Array eingelesen. Dabei ist wichtig, dass solch ein durch Kopie von 1 Spalte des Arbeitsblatts gefülltes Array zwar einspaltig zu sein scheint aber auf jeden Fall wie ein mehrspaltiges Array angesprochen werden muss: aArray(1,1) spricht das erste Element an. Und falls Sie jetzt meinen, dass das im Normalfall doch das zweite Element sein müsse, weil ja Arrays (wenn kein Option Base 1 verwendet wurde) typischerweise mit dem Element 0 beginnen, dann sehen Sie hier eine weitere Ausnahme. Durch direktes Einlesen von der Tabelle erstellte Arrays sind immer 1-basiert.

Bleibt noch der Aufruf der Sortier-Routine. Die Sub QSort, welche den Quicksort-Algorithmus enthält, braucht für den Aufruf die „Zeilennummer“ der ersten und der letzten Zeile (Elements) des Arrays. Prinzipiell ließe sich das auch innerhalb der Routine berechnen, aber da diverse rekursive Aufrufe erfolgen, wäre der Rechenaufwand extrem hoch und auch unnütz, weil es sich in einem definierten Array ja um feststehende Werte handelt. – Um nicht bei jedem externen Aufruf der Sub erneut die Übergabeparameter zu schreiben (ich bin nämlich schreibfaul), ist eine kleine Prozedur zwischengeschaltet, welche die erste und die letzte Zeile des Arrays berechnet und diese beiden Werte als Argument an die eigentliche Sortier-Prozedur übergibt:

Sub QuickSortStart(aData)
    Call QSort(aData, LBound(aData), UBound(aData))
End Sub

Sub QSort(aData, a As Long, e As Long)
   Dim x As Long, y As Long, vntTmp As Variant, vntPivot As Variant
   x = a
   y = e
   vntPivot = aData((a + e) \ 2)
   Do While x <= y
      Do While aData(x) < vntPivot
         x = x + 1
      Loop
      Do While aData(y) > vntPivot
         y = y - 1
      Loop
      If x <= y Then
         vntTmp = aData(x)
         aData(x) = aData(y)
         aData(y) = vntTmp
         x = x + 1
         y = y - 1
      End If
   Loop
   If a < y Then Call QSort(aData, a, y)
   If x < e Then Call QSort(aData, x, e)
End Sub

Hinweis: Das Ganze funktioniert ausschließlich mit eindimensionalen Arrays. Dabei ist es keineswegs unerheblich, wie diese gefüllt worden sind. Wenn Sie beispielsweise einen solchen Code verwenden, um das Array zu füllen:

Dim aData(lRow), Ze As Long
For Ze = 2 To lRow
   aData(Ze - 1) = Cells(Ze, Sp)
Next Ze

dann ist das Array (normalerweise) nicht nur nullbasiert, es ist auch „echt“ einspaltig. Dadurch sprechen Sie das erste Element so an:

Wert = aData(0)

Und vor allen Dingen: Der Teil

'So eingelesene Arrays müssen mehrdimensional angesprochen werden
'Darum Transfer in ein 1-dimensionales Array
ReDim aData(UBound(MyData)) 
For i = 1 To UBound(MyData) 
   aData(i) = MyData(i, 1)
Next i

aus dem SortierTest() ist natürlich überflüssig; es liegt ja schon ein eindimensionales Array vor und muss nicht erst aus dem mehrdimensionalen konvertiert werden. – Natürlich können Sie auch ein leeres Tabellenblatt erstellen oder verwenden, dort die zu sortierenden Daten hinein kopieren, sortieren und dann und das Array zurückschreiben. Diese Lösung ist vielfach für mehrspaltige Arrays/Bereiche empfehlenswert.

▲ nach oben …

 

Dieser Beitrag wurde unter Coding / Programmieren, Musterlösungen abgelegt und mit , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.