Glengamoi (Forum) · AspHeute · .NET Heute (RSS-Suche) · AspxFiles (Wiki) · .NET Blogs

Sortieren von Arrays in VBScript

Geschrieben von: Stefan Gründhammer
Kategorie: ASP Tricks

This printed page brought to you by AlphaSierraPapa

In diesem Artikel werden Sie lernen Elemente in einem eindimensionalen Array zu sortieren, da dies hin und wieder von großen Nutzem ist. Da VBScript keine passende Funktion und auch keine Sortierbefehle zur Verfügung stellt, müssen wir auf das gute alte Selberprogrammieren zurückgreifen. Ich werde Ihnen zwei bekannte Sortieralgorithmen vorstellen. Wir werden Beispiele mit dem sehr weit verbreiteten Bubble-Sort-Algorithmus und einem älteren, aber dennoch sehr schnellen Alogorithmus, dem Quick-Sort-Algorithmus ausprogrammieren und besprechen.

Vorbereitung

Jeder fortgeschrittene ASP-Programmierer sollte sich mit Arrays auskennen, ich setze also voraus, daß Sie bereits einmal ein Array dimensioniert haben und auch wissen was ReDim und das Zauberwort Preserve bewirken. Infos zu dynamischen Arrays finden Sie im Artikel Dynamische Arrays - Fluch und Segen.

Ich werde mich in diesem Artikel auf eindimensionale Arrays konzentrieren, da diese ausreichen, um die Algorithmen der Sortierung zu beschreiben. Natürlich geht das Sortieren auch mit mehrdimensionalen Arrays.

Nehmen wir folgende Problemstellung an: Sie haben 500 unsortierte Zahlen in einem Array und wollen eine Ordnung dieses Haufens. Wie machen Sie das am schnellsten und elegantesten? Wenn Sie ein Array mit 500 Einträgen händisch sortieren müßten, würden Sie sicher einige Stunden damit verbringen. Deshalb wäre es doch toll ein kleines Programmlein zu haben, das uns die Arbeit abnimmt und noch dazu die Arbeit in Sekundenbruchteilen erledigt.

Sortieralgorithmen

Es gibt bestimmt hunderte Sortieralgorithmen, aber nur wenige die sich so gut zum einfachen und schnellen Sortieren von Arrays eignen wie Bubblesort und Quicksort. Oft ist es schneller, einfache Algorithmen zu nutzen als sich mit komplexen Mehrzweckverfahren herumzuschlagen. In der Regel benötigen einfache Sortieralgorithmen ungefähr N² Schritte zum Sortieren von N zufällig angeordneten Elementen. Wenn die Menge der Elemente hinreichend klein ist und die Elemente nicht zufällig angeordnet sind, sortieren einige der einfachen Sortierverfahren schneller als die komplizierten.

Bubblesort

Einer der bekanntesten und einfachsten Algorithmen ist der Bubblesort-Algorithmus, er wird in nahezu jedem einführenden Programmierkurs lang und breit diskutiert. Dieser Algorithmus durchläuft das zu sortierende Array, wobei immer zwei benachbarte Elemente miteinander verglichen und wenn nötig auch ausgetauscht. Sortiert ist das Array dann, wenn kein Vertauschen zweier benachbarter Elemente im Array mehr nötig ist.

Ich habe zur Demonstration dieses Verfahrens ein kurzes Script (bubblesort_1.asp), welches Sie sich mittels Link am Ende dieses Artikels downloaden können, geschrieben, in dem Sie z.B. einen String sortieren lassen können, in dem die Elemente durch Leerzeichen voneinander getrennt sind (Sie können das Trennzeichen natürlich auch abändern und an Ihr Script anpassen).

  
 ...
 
 6: function bubblesort(arrSortieren)
 7:   for i = 0 to ubound(arrSortieren)
 8:     for j = i + 1 to ubound(arrSortieren)
 9:       if arrSortieren(i) > arrSortieren(j) then
10:         arrTemp = arrSortieren(i)
11:         arrSortieren(i) = arrSortieren(j)
12:         arrSortieren(j) = arrTemp
13:       end if
14:     next
15:   next
16:   bubblesort = arrSortieren
17: end function

 ...

44: arrSort = bubblesort(arrTest) 
45:
46: for x = 0 to ubound(arrSort)
47:   response.write "arrSort" & "("& x & ") enthält " & x & "<br>"
48: next

In Zeile 44 wird die Funktion bubblesort aufgerufen. In der Funktion bubblesort wird das Array arrSortieren initialisiert. In Zeile 7 beginne ich eine For...Next-Schleife, welche von 0 bis zu UBound(arrSortieren) läuft. Geschlossen wird diese Schleife in Zeile 15. Innerhalb der ersten Schleife befindet sich noch eine zweite For...Next-Schleife (von Zeile 8 bis 14) in der ich der Variable j den Wert i+1 zugewiesen habe, in den Zeilen 9 bis 13 kommt es zum Vergleichen der einzelnen Einträge auf Größe und zum Sortieren der Einträge gegeneinander. Mit arrTemp führe ich eine temporäre Hilfsvariable ein, welche ich zum Zwischenspeichern von Werten während des Vertauschens zweier Werte des Arrays brauche.

Wir durchlaufen das Array von ersten bis zum (n-1)-ten Element. Wenn der Wert von Array(i+1) kleiner ist als der Wert von Array(i), dann wird Array(i) mit Array(i+1) vertauscht. Um das Array sicher sortieren zu können müssen wir diese Vergleiche (n-1) mal durchlaufen.

Das Gute am Datentyp Variant (von VBScript verwendet) ist, daß man ohne Probleme Daten jedes beliebigen Typs, Währungen, Zeichenketten etc. aufsteigend oder absteigend ordnen kann.

Die Laufzeit des Bubblesort Verfahrens kann man hinreichend genau mit N² bestimmen.

Nun möchte ich den nächsten Algorithmus, der in seiner Gewschwindigkeit nicht zu unterschätzen ist, erläutern.

Quicksort

Dieser Algorithmus beruht auf dem Prinzip "Teile und Herrsche" und funktioniert wie folgt: Man teile die Datei bzw. das Array in zwei Teile und sortiere diese unabhänging voneinander und dann werden beide Teile wieder zusammengefügt. Etwas genauer sollte man sich das Sortieren als halbieren der Hälften vorstellen und zwar solange bis nur mehr zwei Teile sind dann dann vertauscht werden können.

Speichern Sie nun die Datei quicksort.asp auf Ihrer Maschine ab und starten Sie es. Die Fehlerbehandlung dieses Script ist nicht sehr aufwendig gestalltet, sollte aber zur Erklärung dieses Beispiels ausreichen.

 
 ...
 
 4: Sub quicksort(mitt, anfang, ende)
 5:   Dim hilf, obenTau, untenTau, temp
 6: 
 7:   if ende - anfang = 1 And mitt(anfang) > mitt(ende) Then
 8:       temp=mitt(anfang)
 9:       mitt(anfang) = mitt(ende)
10:       mitt(ende) = temp
11:   End If
12: 
13:   ' Mehr als 3 Elemente muessen sortiert werden
14:   hilf = mitt(int((anfang + ende) / 2))
15:   mitt(int((anfang + ende) / 2)) = mitt(anfang)
16:   mitt(anfang) = hilf
17:   obenTau = anfang + 1
18:   untenTau = ende  
19:   
20:   do
21:       'Finden von obenTau
22:       while obenTau < untenTau and mitt(obenTau) <= hilf
23:       obenTau = obenTau + 1
24:       wend
25:
26:       'Finden von untenTau
27:       while mitt(untenTau) > hilf
28:       untenTau = untenTau - 1
29:       wend
30:       'Vertausche die Werte wenn obenTau kleiner als untenTau 
31:       if obenTau < untenTau then
32:       temp = mitt(obenTau)
33:       mitt(obenTau) = mitt(untenTau)
34:       mitt(untenTau) = temp
35:       End If
36:   loop while obenTau < untenTau
37:   
38:   mitt(anfang) = mitt(untenTau)
39:   mitt(untenTau) = hilf
40:   'Aufruf der Sub rekursiv
41:   'Sind zwei oder mehr Elemente in der ersten Teilmenge
42:   if anfang < (untenTau - 1) then 
43:     Call quicksort(mitt,anfang,untenTau-1)
44:   end if
45: 
46:   'Sind zwei oder mehr Elemente in der zweiten Teilmenge
47:   if untenTau + 1 < ende then 
48:     Call quicksort(mitt,untenTau+1,ende)
49:   end if
50: End Sub

...

In Zeile 4 beginnt der eigentliche Algorithmus und reicht mit einigen kleinen Ausnahmen bis Zeile 50. In den Zeilen 46 bis 51 vertausche ich die Werte der Variablen anfang und ende wenn ende kleiner als anfang ist, um die aufsteigende Sortierung gewährleisten zu können. Die selbe Prozedur geschieht in den Zeilen 13 bis 18 bei drei oder mehr Elementen. Das eigentliche Sortieren geschieht in den Zeile 20 bis 36 mittels do..loop-Schleife und einer darin verschachtelten If-Schleife.

Und das Schöne an diesem Algorithmus ist in den Zeilen 42 bis 49, das rekursive Aufrufen der einzelnen Teilprozeduren bis das Array sortiert ist.

Im nächsten Codeblock werden eigentlich nur die Ausgaben und Erzeugung der Zufallzahlen besprochen, die nähere Erklärung folgt unterhalb.

 
...

52: 'Anzeigen des Arrays
53: Sub ZeigeArray(mitt,lo,hi)
54:   Dim i
55:    For i = lo to hi
56:      Response.Write mitt(i) & "<br>"
57:    Next
58: End Sub 
 
 ...
 
109: Randomize
110: sAnzahl = Anzahl-1
111: reDim Arr(sAnzahl)
112: For z = 0 to sAnzahl
113:   Arr(z) = int(Rnd*100)
114:   If (Rnd < 0.5) then 
115:   Arr(z) = Arr(z)-100
116:   end if
117: Next
118: 
119: Response.Write "<h2>Hier ist Ihr unsortiertes Array</h2>"
120: Call ZeigeArray(Arr,0,sAnzahl)
121: 
122: Call quicksort(Arr,0,sAnzahl)
123: 
124: Response.Write "<h2>Jetzt ist es mit dem " & _
125:      "Quicksort-Algorithmus sortiert worden!</h2>"
126: Call ZeigeArray(Arr,0,sAnzahl)

...

Das Anzeigen des Arrays erfolgt in von Zeile 53 bis 58. Dieser Block ist für die Ausgabe des sortierten und auch des unsortierten Arrays (zur Arbeitserleichterung) zuständig. Die Prozedur wird in den Zeilen 120 und 126 zur Ausgabe des Arrays aufgerufen.

Die Zufallszahlen, mit welche das Array in diesem Beispiel befüllt wird, generiere ich in den Zeilen 109 bis 117, wobei ich, um eine größere Vielfalt an Zahlen zu erreichen, auch negative Zahlen erzeuge.

Wenn man es genau nimmt sieht man eigentlich nur die Arbeit, welche in den Zeilen 119 bis 126 ausgeführt wird. Die Verwendung des Quicksort-Algorithmus verlangt schon um einiges mehr Aufwand vom Programmierer als der Bubblesort Algorithmus.

Schlußbemerkung

Dadurch, daß VBScript keine eigene Funktion und auch keinen Befehl für die Sortierung bereitstellt, müssen wir uns selber helfen. Sie haben in diesem Artikel gelernt wie man ein ein-dimensionales Array sortiert. Dabei habe ich Ihnen anhand zweier Sortieralgorithmen gezeigt, wie man Arryas mit verschiedenen Datentypen sortiert.

Die einfachere Version der Sortierung ist zweifelsohne der Bubblesort-Algorithmus. Er ist leicht und schnell auf Ihre Aufgabe angepasst und führt Sortierungen von kleinen Arrays hinreichend schnell aus. Sollten Sie allerdings große Arrays sortieren müssen, und das noch dazu mehrere Male, dann empfehle ich Ihnen, sich etwas Arbeit anzutun und die Sortierung mit Quicksort durchzuführen. Noch viel Spaß beim Sortieren.