Sortieren von Arrays in VBScript
Geschrieben von: Stefan Gründhammer 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. VorbereitungJeder 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. SortieralgorithmenEs 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. BubblesortEiner 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. QuicksortDieser 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ßbemerkungDadurch, 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. Download des CodesKlicken Sie hier, um den Download zu starten. Verwandte Artikel
Am Server installierte Schriftarten auslesen Wenn Sie jetzt Fragen haben...Wenn Sie Fragen rund um die in diesem Artikel vorgestellte Technologie haben, dann schauen Sie einfach bei uns in den Community Foren der deutschen .NET Community vorbei. Die Teilnehmer helfen Ihnen gerne, wenn Sie sich zur im Artikel vorgestellten Technologie weiterbilden möchten. Haben Sie Fragen die sich direkt auf den Inhalt des Artikels beziehen, dann schreiben Sie dem Autor! Unsere Autoren freuen sich über Feedback zu ihren Artikeln. Ein einfacher Klick auf die Autor kontaktieren Schaltfläche (weiter unten) und schon haben Sie ein für diesen Artikel personalisiertes Anfrageformular.
Und zu guter Letzt möchten wir Sie bitten, den Artikel zu bewerten. Damit helfen Sie uns, die Qualität der Artikel zu verbessern - und anderen Lesern bei der Auswahl der Artikel, die sie lesen sollten.
©2000-2006 AspHeute.com |