Sortierroutinen werden oft benötigt und noch öfter neigen (Gelegenheits-) Programmierer dazu, aus purer Bequemlichkeit kurze, aber schlechte Algorithmen vorzuziehen, wo es nur unwesentlich längere, aber viel bessere gibt. Hier im Kurs etwa wurde zur Datenauswertung das wohl langsamste aller wirklichen Sortierprogramme Bubble-Sort (Bubble zu deutsch Blase, erinnert an aufsteigende Blasen im Wasser) verwendet.
Wieso wirklich?
Weil es auch Nicht-Sortierverfahren, wie Bozo-Sort gibt, bei welchem nur zufällig herausgegriffene Wertepaare vertauscht werden, bis die Reihenfolge stimmt. Kleine Kostprobe folgt, ein Java-Applet, seien Sie bei der Zahl der zu sortierenden Werte vorsichtig!:
Langsame Sortierverfahren sind bei kleinen Datenfeldern kein Problem.
Wenn es aber um sehr große Datenfelder geht, muß man sowohl die Geschwindigkeit als auch den erforderlichen Speicherplatz im Auge haben. Einige der bekannten Sortieralgorithmen sollen hier vorgestellt und bezüglich Geschwindigkeit und Speicherbedarf miteinander verglichen werden.
Für die Testung gilt: Ein Array a(n) wird anfänglich mit Zufallszahlen gefüllt. Der Aufruf der Sortierroutinen erfolgt jeweils mit der Zahl zu sortierender Datensätze n (= gewünschte Datenfeldgröße) und dem Vektor a(n), der die Datensätze enthält.
| 'Deklaration im Modulkopf Global .... , a(gewünschte Datenfeldgröße) As gewünschter Datentyp, ... ... Sub ShellSort(ByVal n As Long, a() As gewünschter Datentyp) Dim i As Long, j As Long, delta As Long, elem As Long delta = 1 Do delta = 3 * delta + 1 Loop Until delta > n Do delta = delta \ 3 For i = delta + 1 To n elem = a(i) j = i Do While a(j - delta) > elem a(j) = a(j - delta) j = j - delta If j <= delta Then Exit Do Loop a(j) = elem Next i Loop Until delta = 1 End Sub |
Schneller als das beschriebene Sortierprogramm arbeitet Heapsort. Ein "Heap" ist zu deutsch ein Haufen, eine Datenstruktur, die bei der Sortierung als Hilfe dient.
Die genaue Funktion zu erläutern würde hier zu weit führen. Nur soviel:
Im ersten Programmteil wird der Heap erzeugt, eine sehr pfiffige Angelegenheit, denn er enthält selber eine Baumstruktur von Heaps.
Im zweiten Teil werden die Elemente in der Reihenfolge ihrer Größe aus dem Heap entnommen und in ihre endgültige Position gebracht.
| Sub HeapSort(ByVal n As Long, a() As gewünschter Datentyp) Dim i As Long, j As Long, k As Long, l As Long Dim t As Long, v As gewünschter Datentyp Dim m As Long m = n For l = n \ 2 To 1 Step -1 k = l t = a(k) Do While k <= n \ 2 j = k + k If j < n Then If a(j) < a(j + 1) Then j = j + 1 End If If t >= a(j) Then Exit Do a(k) = a(j) k = j Loop a(k) = t Next l Do v = a(1) a(1) = a(m) a(m) = v m = m - 1 k = 1 t = a(k) Do While k <= m \ 2 j = k + k If j < m Then If a(j) < a(j + 1) Then j = j + 1 End If If t >= a(j) Then Exit Do a(k) = a(j) k = j Loop a(k) = t Loop Until m <= 1 End Sub |
In a() liegen die zu sortierenden Daten, der gewünschte Datentyp ist im Kopf wie im Deklarationsteil einzutragen. Es können alle Arten von Zahlen aber auch Strings sein. Matrixstrukturen (Tabellen) könnten nach dem Inhalt einer Spalte oder mehrerer Spalten sortiert werden. In diesem Falle ist allerdings Sorge füe die ordnungsmäßige Umspeicherung auch des Restes des Datenfeldes zu sorgen.
Wie immer wird bei der Sortierung von Texteinträgen nach der Reihenfolge der ASCII-Werte sortiert. Der Aufruf für n Elemente erfolgt mit: HeapSort n, a()
Als eines der schnellsten Sortierverfahren, wenn nicht als schnellstes überhaupt, gilt Quicksort. Die Idee ist, die zu sortierende Elementemenge in zwei Teile zu teilen und beide getrennt zu sortieren. Diese Sortierungen erfolgen, indem man die Elementemenge(n) in zwei Teile teilt .... das heißt Rekursion, wie sie schon bei der Fakultätsberechnung benutzt wurde. Die Sache endet, wenn es nichts mehr zu teilen gibt.
| Sub QuickSort(ByVal l As Long, ByVal r As Long, a() As Long) Dim i As Long, j As Long, m As Long Dim t As Long i = l j = r m = a((l + r) \ 2) Do Do While a(i) < m i = i + 1 Loop Do While m < a(j) j = j - 1 Loop If i <= j Then t = a(i) a(i) = a(j) a(j) = t i = i + 1 j = j - 1 End If Loop Until i > j End SubIf l < j Then QuickSort l, j, a() If i < r Then QuickSort i, r, a() |
Kurze Erläuterung:
In a() liegen die zu sortierenden Daten, im Beispiel sind es Long Integers. Hier ist Anpassung an den zu sortierenden Datentyp erforderlich, es können alle Arten von Zahlen aber auch von Strings sein. Bei der Sortierung von Texteinträgen wird nach dem ASCII-Wert bzw. der Folge der ASCII-Werte sortiert. Auch die Hilfsgröße t muß den zu sortierenden Datentyp erhalten.
l (für links) und r stehen für die Grenzen eines zu sortierenden Teilfeldes. Der Gesamtaufruf für n Elemente erfolgt mit: QuickSort 1, n, a().
Moderne Rechner sind so schnell, daß man ihnen ein "Protokoll" ihrer Tätigkeit abverlangen kann. Klassische (Großrechner-)Programmierer haben das für neue Programme schon immer so gemacht und damit in der Testphase viele Kilogramm Papier verbraucht. Wir können aber heute unter hinnehmbaren Abstrichen bei der Rechengeschwindigkeit die Grafikkarte strapazieren und duchaus auch optisch reizvolle Anzeigen während der Rechenarbeit erzeugen.
Was man an welcher Stelle des Programmes anzeigt, bleibt dem Programmschöpfer überlassen. An dieser Stelle wird als Beispiel eine Möglichkeit beschrieben, wie man die nicht einfach zu verstehende Arbeitsweise der Sortierprogramme verdeutlichen kann.
Nehmen wir an, das zu sortierende Datenfeld a() bestehe für Datensortierungen aus Zahl Zufallszahlen, deren Größen zwischen 0 und Spanne liegen. Wenn die nacheinander, also unsortiert, in ein Array geschrieben werden, läßt sich dieses in einem Fenster mit Hilfe von Punkten darstellen: Y-Wert sei der Zufallswert, X-Wert die Wertenummer. Es entsteht eine Art Sternenhimmel. Das hier dunkle Blau des Hintergrunds ist die BackgroundColor des Picture1-Elements, vorgewählt im Eigenschafts-Fenster.
| Bild vorbereiten und Daten erzeugen: Picture1.Scale (0, Spanne)-(Zahl, 0) n = 0 For i = 1 To Zahl n = n + 1 Nexta(n) = Int(Rnd * Spanne.Height) Daten erstmalig darstellen: Sub Male(i As Long, a() As Long) Dim j As Long Form1.Picture1.Cls For j = 1 To i Form1.Picture1.PSet (j, a(j)), QBColor(14) Next End Sub |
So etwa sieht das dann für 10000 Werte aus:
Für die Abbildung des Sortierverlaufes muß nun zu jeder Punkteverschiebung bzw. zu jedem Punktetausch innerhalb des Arrays die alte Position jeden Punktes gelöscht und die neue gemalt werden. Wie das im Code aussieht, sei hier am Beispiel von Bubblesort gezeigt, das am Beginn dieser Seite erwähnt und dessen Algorithmus bei der Datenauswertung benutzt worden ist.
Die Vorgehensweise: Am Feldende beginnend, vergleicht man jedes Element mit seinem Vorgänger und vertauscht beide, wenn nötig, miteinander. Auf diese Weise werden die kleineren Elemente nach unten "gekämmt", während die größeren notgedrungen "aufsteigen". Beim ersten Durchlauf gerät das absolut kleinste Element auf Platz 1. Von unten nach oben wächst bei weiteren Durchläufen die Zahl der endgelagerten Elemente.| Sub Bubble(lo As Long, hi As Long, a() As Long) For j = hi To lo + 1 Step -1 For i = lo To j - 1 If a(i) > a(i + 1) Then Form1.Picture1.PSet (i, a(i)), &H800000 Form1.Picture1.PSet (i + 1, a(i + 1)), &H800000 t = a(i) a(i) = a(i + 1) a(i + 1) = t Form1.Picture1.PSet (i, a(i)), QBColor(14) Form1.Picture1.PSet (i + 1, a(i + 1)), QBColor(14) End If Next Next End Sub |
Unten das Bild. Die Punkte werden in quälender Langsamkeit scheinbar am unteren gerundeten Rand entlang in ihre endgültige Position verschoben.
Es folgt ein Blick in den Ablauf der Sortierung mittels Shellsort. Die Punkte werden in mehreren Durchgängen auf die Diagonale hin "zusammengeschoben". Eine Momentaufnahme:
Die Sortierung mit Heapsort in der Phase der Aufarbeitung des Heap:
Nächstes Bild. Quicksort, der Spitzenreiter in Aktion:
