vb@rchiv · Workshops · Sortierverfahren

Rubrik: Allgemein | VB-Versionen: VB5, VB6

15.02.04

Sortierverfahren Dieser Artikel soll einen kleinen Einblick in die Programmierung von Sortierverfahren unter Microsoft Visual Basic geben (Theorie und praktische Anwendung).
Autor: Martin Reiche	Bewertung:	Views: 24.284

Dieser Artikel soll einen kleinen Einblick in die Programmierung von Sortierverfahren unter Microsoft Visual Basic geben (Theorie und praktische Anwendung).

Aufgabe 1: Planung des Projektes

Natürlich sollte man die Programmierung in mehreren Stufen vollziehen:

Welche Elemente sollte ich zweckmäßigerweise für die Programmierung verwenden?
Man sollte wissen, welche Elemente von Natur aus schnell genug sind, um eine große Anzahl von Elementen hineinzuschreiben.
Wie funktionieren die Elemente, wie greife ich auf sie zu?
Auch dies ist wichtig, denn ein Element, mit dem man nicht umgehen kann, hilft einem herzlich wenig.
Überlegung eines geeigneten Algorithmus (in unserem Fall: BubbleSort)
Ich habe mich für BubbleSort entschieden, da er der einfachste Sortieralgorithmus und somit sehr leicht umzusetzen ist.
Implementierung des Algorithmus
Nur ein in der Praxis funktionierender Algorithmus ist ein guter Algorithmus. Deshalb sollte man vor allem bei der Implementierung Fehlerquellen vermeiden.
Implementierung der Funktionen zur Zeitmessung, um Aufschluss über die Geschwindigkeit des Sortieralgorithmusses zu bekommen
Dies ist die einzig sinnvolle Variante, die Leistung seines Programms mit der Leistung anderer Programme zu vergleichen.
Design
Nicht unbedingt notwendig, aber hilfreich für den Endbenutzer.

Aufgabe 2: Überlegung und Programmierung

Teil A

Der Zugriff auf das VB-Listensteuerelement Listbox ist im Allgemeinen einfach. Folgende Befehle und Eigenschaften sind für die Programmierung des Sortierprogramms erforderlich/nützlich:

Funktionen:

Objekt.AddItem(Item as String, [Index])
Fügt ein Element der Liste hinzu

Objekt.RemoveItem(Index as Integer)
Löscht ein Element aus der Liste

Objekt.Clear
Löscht den Inhalt der gesamten Liste

Eigenschaften:

Objekt.List(Integer) as String
Gibt den Text des markierten Listenelementes zurück

Objekt.Text as String
Gibt auch den Text des markierten Listenelementes zurück

Teil B

Die Liste kann mit dem Bubble-Sortierverfahren sortiert werden. Dies ist das schlechteste aber einfachste Sortierverfahren. Es funktioniert wie folgt:Immer zwei in der Liste aneinander liegende Elemente werden verglichen. Je nach Sortierkriterium werden die Einträge dann vertauscht oder nicht. Hier ein VB-Quellcode-Beispiel zum Vertauschen der Inhalte zweier Variablen:

Entry1 ist Listeneintrag 1 und Entry2 Listeneintrag 2.

Dim Buffera as String
Buffera = Entry1
Entry1 = Entry2
Entry2 = Buffera

Der Puffer (Buffer) ist unbedingt erforderlich, da sonst der Inhalt des ersten Listeneintrags verloren gehen würde. Dies geht natürlich auch für eine ganze Liste: Der Quellcode dazu ist zwar etwas länger, funktioniert aber nach dem gleichen Prinzip.

Als Allererstes kommen ein paar Deklarationen:

Dim texxt(100000) As String 
Dim temporaer As String   ' das wird mal der Buffer
Dim nochwas As Boolean          
Dim anzahl As Long
Dim anz

Jetzt müssen den Variablen noch Werte zugewiesen werden:

anzahl = liste.ListCount
For v = 0 To liste.ListCount
  texxt(v) = liste.List(v)
Next
anz = UBound(texxt)

Alles, was hier passiert, ist, dass "anzahl" mit der Anzahl der Elemente der Liste gefüllt wird, "texxt" erhält den Inhalt aller Einträge (wie wichtig sind doch die Arrays...) und "anz" erhält den "UBound", also den höchsten Wert im Array (praktisch identisch mit "anzahl -1").

Jetzt zum eigentlichen Sortieralgorithmus:

Zuerst brauchen wir eine For...Next-Schleife, in die eine zweite For...Next-Schleife verschachtelt wird. In dieser zweiten Schleife befindet sich der Teil, in dem das Programm prüft, ob das Element, das jeweils darunter liegt (a+1), kleiner ist und, falls erforderlich, die beiden Elemente vertauscht:

For ii = 1 To liste.ListCount
  For a = 0 To anzahl - 1
    If texxt(a) > texxt(a + 1) Then
      temporaer = texxt(a)
      texxt(a) = texxt(a + 1)
      texxt(a + 1) = temporaer
      nochwas = True
      vps = vps + 1
    End If
  Next

Dann findet noch eine Überprüfung statt und schließlich wird auch die erste (ii) For...Next-Schleife wieder beendet.

If nochwas = False Then Exit For
 
Next ii

"nochwas" diente immer zur Überprüfung, ob die Sortierung bereits vollständig abgeschlossen ist oder noch Elemente unsortiert sind. Wenn "nochwas" wahr ist, gibt es noch unsortierte Elemente. Alle Veränderungen an der Reihenfolge der Listeneinträge sind nur in der Form erfolgt, dass die Elemente im Array getauscht wurden. Jetzt müssen wir nur noch das Array auf die Liste übertragen und fertig:

liste.Clear
 
For a = 0 To Int(anzahl)
  If Not texxt(a) = "" Then
    liste.AddItem texxt(a)
  End If
Next

Und das war es.

Teil C

Die Effizienz eines Sortierverfahrens kann durch Zeitmessung am besten festgestellt werden: Man nimmt die Zeit vor dem Sortieren und nach dem Sortieren über den Aufruf "Timer" und berechnet anschließend die Differenz.

Mein Sortieralgorithmus (BubbleSort) erreicht etwa folgende Werte:

bei 10 000 unsortierten Einträgen: 23,6 Sekunden / ca. 25.151.808 Tauschvorgänge
bei 1000 unsortierten Einträgen: 0,23 Sekunden / ca. 257.115 Tauschvorgänge /macht 1.117.891 Tauschvorgänge pro Sekunde
bei 100 unsortierten Einträgen ist die Dauer nicht mehr messbar, da sie zu kurz ist.

Diese Werte stammen von einem Testlauf auf meinem Athlon XP 2600+ mit 512 MB DDR-RAM.

Praktisch nimmt man die Zeit so:

Vor dem Sortieren:

Variable1 = Timer

Nach dem Sortieren:

Variable2 = Timer
Zeit = Variable2 - Variable1

Alle Variablen sollten als Double deklariert sein, da eine Fließkommazahl mit doppelter Genauigkeit nun einmal die besten Ergebnisse liefert.

Man kann aber auch noch einen Tauschvorgangs-Zähler einbauen. Bei jedem Tauschvorgang wird der Zähler dann um eins erhöht (Inkrement). Wenn die Sortierung abgeschlossen ist, enthält diese Variable die Anzahl der Tauschvorgänge und kann diese dann durch die Anzahl der Sekunden teilen. Damit würde man dann die "Tauschvorgänge pro Sekunde" bekommen; der beste Wert zum Feststellen der Effizienz und zum Vergleich mit anderen Sortier-Programmen.

Teil D

Das Sortierverfahren, das oben als Quellcode steht, ist an sich zu langsam. Um es zu verbessern gäbe es die folgenden Möglichkeiten:

Ausblenden der Listbox während der Sortierung brachte bei mir eine enorme Verbesserung der Geschwindigkeit (bei 100 Einträgen waren es 80 %).
Erstellen von zwei Gruppen: In die erste kommen alle Einträge, deren Inhalt über "Einträge mal 0,5" liegen, in die andere Gruppe alle anderen: Ähnlich dem QuickSort-Verfahren. Erst wird der höchste Listenwert gesucht (durch Vergleichen und Austauschen, wenn nötig) und dieser dann durch 2 geteilt (und danach mit Fix() in eine Ganzzahl verwandelt [optional]). Nun werden alle Werte der Liste, die kleiner als die eben gewonnene Zahl sind, in ein erstes Array geschrieben und alle anderen in ein zweites. Diese beiden Teile werden dann sortiert und schließlich wieder zusammengefügt. Da die benötigte Zeit ja exponentiell wächst, kann man mit dieser Methode eine Menge Zeit sparen.
Das kleinste Element wird gesucht und an den Anfang gesetzt. Die restlichen Elemente werden dann logischerweise eins nach unten verschoben. Dann wird das zweitkleinste Element gesucht und direkt unter das erste gesetzt. Dies wird solange wiederholt, bis die Liste (o. Array) sortiert ist.

Teil E

Andere schnellere Sortierverfahren sind zum Beispiel:

QuickSort
Dieser Sortieralgorithmus geht rekursiv nach dem "Devide-and-conquer"-Prinzip vor. Die Menge der zu sortierenden Elemente wird in zwei Teilstücke zerteilt (Devide). Dann werden beide Teile rekursiv (= Math. zurückgehend bis zu bekannten Werten) sortiert. Das funktioniert folgendermaßen: Es wird ein Vergleichselement x gewählt, das mit jedem Element verglichen wird. Alle Elemente, die kleiner sind als x, kommen in Teilstück A. Alle Elemente, die größer sind als x, kommen in Teilstück B. Am Ende setzt man die beiden Teile wieder zusammen und erhält somit die sortierte Gesamtmenge.

Austauschverfahren
Das Austauschverfahren geht da schon ganz anders vor. Jedes Listenelement wird jeweils mit jedem anderen Element verglichen und wenn nötig vertauscht. Nach der Vertauschung wird mit dem neuen Wert des Listeneintrags (des gleichen Index!) weiter verglichen, bis man am Ende der Liste angekommen ist.

Quellen:
"QuickSort in VB" von Dieter Otter aus VB@rchiv CD Vol.3 Jubiläumsausgabe; www.vbarchiv.net
Duden Band 1; Dudenverlag
Sortieralgorithmen von Joachim Röhl; home.t-online.de/home/achim.roehl/vb.htm