Aufgrund der positiven Resonanz, die ich als Antwort auf den ersten Teil meines Tutorials "Algorithmus Optimierung in Visual Basic" bekam, habe ich mich entschlossen einen zweiten Teil zu liefern. Da sich der erste Teil mit einem Primzahlenprogramm beschäftigte, dies allerdings mehr mit Programm- als mit Algorithmus-Optimierung zu tun hat, werde ich mich nun mit reinen Algorithmen beschäftigen. Kurz vor dem Beginn mit den Beispielen werde ich noch auf die theoretische Leistungsanalyse von Algorithmen eingehen. Zudem wird dies vollständig durch eine Laufzeitangabe, oder besser durch eine praktische Leistungsanalyse. Ich hoffe, dass ich erneut die Erwartungen meiner Leser erfüllen kann und freue mich natürlich über alle Arten von Meinungsäußerungen, insofern sie konstruktiv sind. Um die erzielten Werte zu vergleichen, hier die Attribute von meinem PC. Leider immer noch der Gleiche...
700MHz AMD Athlon
265 MB RAM
Geforce 256 mit 32 MB RAM
20 GB Festplatte mit 5400 U/Min

Mit freundlichen Grüßen
Klaus Neumann
 Klaus@3000interaktiv.de
www.3000interaktiv.de

Inhalt

	Einführung
	Allocationsort
	Bubblesort
	Insertionsort
	Selectionsort
	Heapsort
	Shellsort
	Quicksort
	Intersort
	Fazit, Analyse
	Nachwort

Wie oben erwähnt, beschäftigt sich dieses Tutorial mit der theoretischen- und praktischen Leistungsanalyse von Algorithmen. Der erste Teil handelte im wesentlichen von der Verbesserung eines strukturell festgelegten Algorithmus. Das Ganze vor dem Hintergrund der Primzahlen. In diesen Teil, beschäftigen wir uns mit Sortierverfahren. Unser Ziel soll sein, mehrere Arten des Sortierens kennen zu lernen und diese unter Verwendung einer einheitlichen Schnittstelle einer Leistungsanalyse zu unterziehen.
Unser Interface soll so aussehen:

Private Sub Bezeichner (Elemente As Long) 
'Bezeichner = Name des Unterprogramms.
'Elemente = Menge der zu sortierenden Zahlen.

Listing 1

Außerdem möchte ich Ihnen noch die theoretische Leistungsanalyse näher bringen. Hierfür verwende ich aber kein Sortierverfahren, sondern ein eher simples Programm.

Theoretische Leistungsanalysen

Theoretische Leistungsanalysen sind von Vorteil, wenn wir uns klar machen wollen, wie der Verlauf einer Performancekurve bei/in allen denkbaren Zuständen/Situationen ist. Stichproben, wie wir sie gegen Ende des Tutorials nehmen werden, sagen nichts über den kompletten Verlauf aus. So kann es stets von Nöten sein eine theoretische Leistungsanalyse durchzuführen.

Wie wir im ersten Teil bereits erkannt haben, sollte man sich nicht mit dem erst besten Algorithmus zu Frieden geben, denn man kann in der Leistung sehr große Unterschiede erkennen. Wir wollen uns nun einer Aufgabe stellen, welche wir theoretisch analysieren können. Unser Programm soll die Gleichung a + b + c = n lösen. Zu Beginn erstelle ich ein Programm, welches alle möglichen Permutation durchgeht.
Hier der Programmcode:

Private Sub gleichung(n As Long)
Dim a, b, c As Long
    For a = 0 To n
        For b = 0 To n
            For c = 0 To n
                If a + b + c = n Then
                    Text1.Text = Text1. Text & _
                    a & " + " & b & " + " & c & " = " & n
                End If 
            Next c
        Next b
    Next a
End Sub

Listing 2

Der Algorithmus spielt jeweils alle Möglichkeiten von 0 bis n und das für a, b und c durch, so dass die Menge Operationen in der Nähe von n³ liegt. Nur durch geringe Variation und einer damit entstandenen Optimierung können wir die Zahl der Operationen von n³ auf n² senken. Der angesprochenen Code sieht nun so aus:

Private Sub gleichung(n As Long)
Dim a, b, c As Long
    For a = 0 To n
        For b = 0 To n
            c = n - (a + b) 
            If a +  b + c = n And c >= 0 Then
                Text1.Text = Text1. Text & _
                a & " + " & b & " + " & c & " = " & n
            End If
        Next b
    Next a
End Sub

Listing 3

Hier schaffen wir es eine Wertzuweisung von c zu bewerkstelligen, um die Zahl der Schleifen zu verringern. Grafisch könnte man sich diese Optimierung wie im Bild unten deutlich machen. Nun erkennt man klar, was dieser Vorgang für Geschwindigkeitsvorteile bringt. Und das ganze bereits ohne einmal die „Stoppuhr“ angelegt zu haben. Bereits bei einem Wert für n = 25 liegt der Unterschied bei ca. 15000 Operationen, das entspricht fast 99%. Ähnlich wie in diesem Beispiel wollen wir nun auch in die anstehenden Sortieralgorithmen angehen. Da die Sortierverfahren etwas komplizierter sind als das Beispiel- Programm, werde ich nicht in jedem Fall auf die Theoretische Leistungsanalyse eingehen wollen und können. Unser Augenmerk soll wie bereits im letzten Teil auf die praktische Temporalanalyse gerichtet sein, um konkrete Werte in der Hand zu haben. Zudem ist noch anzufügen, dass alle Messungen in der IDE durchgeführt wurden.

Abbildung 1: Geschwindigkeitsanalyse

Wir beginnen mit Allocationsort, ein eher langsamer Algorhitmus, welcher aber leicht zu verstehen ist. Der ein oder andere wird sicher schon von selbst auf dieses Verfahren gekommen sein.

Private Sub allocationsort(n As Long)
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear

    Dim i As Long, j As Long, zahlenplatz(1 To 3000) As Long
    Dim daten() As Long
    Dim daten_sortiert() As Long
    
    For i = 1 To n
        For j = 1 To n
            If daten(i) > daten(j) Then
                zahlenplatz(i) = zahlenplatz(i) + 1
            End If
        Next j
    Next i
    
    ' Mittelteil
    For i = 1 To n 
        For j = 1 To n
            If i <> j Then
                If zahlenplatz(i) = zahlenplatz(j) Then
                    zahlenplatz(j) = zahlenplatz(j) + 1
                End If
            End If
        Next j
    Next i
    ' ---
    
    For i = 1 To n
        daten_sortiert(zahlenplatz(i)) = daten(i)
    Next i
    
    For i = 1 To n - 1
        List2.AddItem daten_sortiert(i)
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 4

Hier haben wir es mit einem elementaren Algorithmus zu tun. Sortieralgorithmen, welche lediglich eine Leistungsbeschränkung durch n erfahren werden als allgemein beschrieben. Sie besitzen ein Laufzeitverhalten gegen n². Intersort, welcher gegen Ende des Tutorials folgt, ist zusätzlich durch die verschiedenen Möglichkeiten an Daten eingeschränkt (Speicherbelastung), es wird als speziell beschrieben.

Unterziehen wir den Algorithmus einer theoretischen Leistungsanalyse, so schließen wir auf einen Wert von n² Operationen. Der Wert ergibt sich durch die beiden Schleifen j und i. Denn j * i Durchläufe startet das Programm. Der Wert für i und j ist gleich und beträgt n Elemente, also i = j = n. Nun muss man noch sagen, dass der Algorithmus korrekterweise n² * 2 Operation aufweist, aufgrund der Stabilisierung.

Um das Sortierverfahren genauer zu definieren hat man sich auf einige fundamentale Dinge geeinigt. Der angesprochen Algorithmus ist parallelisierbar , d.h. man kann ihn auf Multiprozessorsystemen implementieren, so das mehrere Rechner gleichzeitig an einem Problem arbeiten. Außerdem ist der Ursprungscode instabil , welches bedeutet, das gleichwertige Schlüsselelemente (Element a ist weder kleiner noch größer als Element b) gegeneinander vertauscht werden können. Das Problem wird durch den obigen als Mittelteil deklarierten Part, aber aufgehoben. . Es lag nämlich in meinem Interresse, dass die Codes die Aufgaben gleichwertig erfüllen. Zudem wird der Allocationsort Algorithmus als Out- of- Place definiert, was konkrete bedeutet das die eigentliche Menge nicht angetastet wird. Genauer: Ein Sortieralgorithmus heißt out-of-place, wenn das Ergebnis der Sortierung in einer neuen Menge zurückgegeben wird. Die Originalmenge wird dann im Allgemeinen nicht verändert. Gerade dadurch wird dieses Verfahren sehr flexibel. Diese Eigenschaft ist zudem leicht implementierbar, da wir immer temporäre Arrays zu Speicherung verwenden können.

Sollte es der Fall sein, dass man von Anfang an weiß, ob Werte doppelt oder mehrfach auftreten so kann man sich den Mittelteil sparen. Allocationsort muss nun die Werte nicht mehr einzeln verschieben. Unsere Leistungsanalyse ergibt folgende Werte für n = 2000:

• Werte können mehrfach auftreten, Zeitmessung: 3880,393 ms
• Werte treten nur einzeln auf, Zeitmessung: 2068,890 ms

Unsere Liste soll auch in den folgenden Beispielen 2000 Elemente besitzen.

Das folgende Beispiel heißt Bubblesort und stellt wohl einen der bekanntesten Sortieralgorithmen überhaupt dar. Die Verbreitung des Algorithmus dürfte allerdings mehr auf der einfachen Methode als auf Effizienz beruhen. Der Algorithmus arbeitet mit dem Prinzip des direkten Austauschs, d.h. aufeinander folgende Schlüssel werden verglichen und gegebenenfalls vertauscht. Das Datenfeld wird nun mehrfach durchlaufen, wobei alle kleineren Schlüssel nach links wandern, alle größeren nach rechts. Stellt man sich das Array senkrecht stehend vor, so erklärt sich der Name Bubblesort mit einiger Phantasie, denn hier steigen die Zahlenwerte ähnlich wie Luftblasen im Wasser auf. Auch Bubblesort hat das gleiche Problem wie Allocationsort. Bereits sortierte Werte werden erneut sortiert, der Algorithmus ist also statisch .
Im Gegensatz zu Allocationsort ist Bubblesort aber ein stabiler Algorithmus. Ebenso ist er parallelisierbar. Bubbelsort ist In-Place. Mit anderen Worten: Man sollte vor dem Sortiervorgang einen temporären Array erstellen, so dass es nicht zu Problemen kommt.

Private Sub bubblesort(n As Long)
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    Dim i, k, t As Long
    
        For i = 0 To n
            daten_sortiert(i) = daten(i)
        Next i
        
        For i = (n - 1) To 0 Step -1
            For k = 0 To i
                If daten_sortiert(k) > daten_sortiert(k + 1) Then
                t = daten_sortiert(k)
                daten_sortiert(k) = daten_sortiert(k + 1)
                daten_sortiert(k + 1) = t
                End If
            Next k
        Next i
        
        For i = 1 To n
            List2.AddItem daten_sortiert(i)
        Next i
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 5

Auch Bubbelsort hat n² Operationen bei der theoretischen Leistungsanalyse ergeben. Erneut aufgrund der 2 Hauptschleifen. Hier k und i.

Dieser elementare Algorithmus ist iterativ, in-place, stabil und parallelisierbar. Iterativ bedeutet hier, dass der Code nicht rekursiv ist, also Schleifen verwendet.

Eine Zeitmessung für dieses Verfahren ergibt einen Wert von, Zeitmessung: 2291,250 ms

Doch kommen wir nun zu einem weiteren sehr bekannten Sortierverfahren, Insertionsort. Insertionsort (auch Insertsort oder Insort genannt) gehört zur Gruppe der elementaren Sortieralgorithmen. Innerhalb dieser Gruppe gehört er zu den effektivsten. Trotzdem ist er noch einfach zu verstehen und iterativ zu implementieren. Dieses Verfahren wird in der Regel auch zur Gruppe der Sortieralgorithmen mit mittlerer Laufzeitkomplexität gezählt. Der Name "Insertionsort" kommt von insertion (dt. Einfügen), da in jedem Schritt ein Element in eine bereits sortierte Gruppe von Elementen eingefügt wird.

Private Sub insertionsort(n As Long)
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    
    Dim i, j, v As Long
    
    For i = 0 To n
        daten_sortiert(i) = daten(i)
    Next i
    
    For i = 1 To n
        v = daten_sortiert(i)
        
        For j = i To 1 Step -1
            daten_sortiert(j) = daten_sortiert(j - 1)
            If daten_sortiert(j - 1) < v Then
                Exit For
            End If
        Next j
        
        daten_sortiert(j) = v
    Next i
    
    For i = 1 To n
        List2.AddItem daten_sortiert(i)
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 6

Für einen elementaren Algorithmus hat Insertionsort sehr interessante Eigenschaften. Es stellt eine Variante dar, welche sicherlich auch für große Anwendungen gebrauchbar ist. Eigenschaften: iterativ, in-place, stabil, parallelisierbar. Ähnlich wie die vorangegangenen Algorithmen hat Insertionsort eine Operationenzahl von n². Allerdings ergibt sich durch die häufigen Schleifenabbrüche eine Zahl von n²/4. i und j stellen wieder einmal die Hauptschleifen dar.

Messen wir nun mit einer praktischen Leistungsanalyse, erhalten wir einen Wert von 1023,733 ms

Kommen wir nun zu dem letzten, hier erwähnten, elementaren Sortieralgorithmus: Selectionsort. Das wohl optimierteste Verfahren unter den Elementaren Sortierverfahren. Die Eigenschaften von Selectionsort sehen so aus: iterativ, in-place, instabil, nicht parallelisierbar. Ein Feld wird einmal vollständig durchlaufen. Dabei wird durch einfache Vergleiche das größte Element herausgesucht (selektiert) und zum Schluss an das Feldende gepackt. Dieser Schritt wird nun mit dem kleineren Teilfeld (Feld ohne das letzte Element) wiederholt und wiederholt und ... und irgendwann sind wir fertig und die Elemente sind sortiert.

Aufgrund der Auswahl von Elementen wird dieses Verfahren auch als "Sortierung durch Auswahl" bezeichnet.

Private Sub selectionsort(n As Long)
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    
    Dim i, k, t, min As Long
    
    For i = 0 To n
        daten_sortiert(i) = daten(i)
    Next i
    
    For i = 0 To (n - 1)
        min = i
        For k = i + 1 To n
            If daten_sortiert(k) < daten_sortiert(min) Then
                min = k
            End If
        Next k
        t = daten_sortiert(min)
        daten_sortiert(min) = daten_sortiert(i)
        daten_sortiert(i) = t
    Next i
    
    For i = 1 To 2000
        List2.AddItem daten_sortiert(i)
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 7

Ähnlich wie die vorherigen Algorithmen ergibt sich eine für Elementare Sortierverfahren typische Laufzeit von n² Operationen. Die Zeitmessung ergibt 949,362 ms .

Heapsort ist ein sehr schneller Algorithmus, welcher auch zu den noch folgenden, eine echte Alternative darstellt. Auch Heapsort benötigt zum optimalen Sortieren ein temporäres Feld. Der Name "Heapsort" kommt von heap und spielt auf seine intern verwendete Haufenstruktur an. Die Idee wurde erstmalig von Williams und Floyd vorgestellt (1964).Heapsort gehört zur Gruppe der asymptotisch optimalen Sortieralgorithmen. Zur Erklärung: Eine asymptotische Laufzeit eines Algorithmus gibt an, wie sich dieser in Abhängigkeit von gewissen Parametern verhält. Solche Parameter sind i.a. die Anzahl und Größe von Ein- und Ausgabeelementen. Algorithmen sind asymptotisch optimale, wenn es nicht möglich ist einen Algorithmus zu konstruieren, der das selbe Problem löst und eine bessere asymptotische Laufzeit besitzt. Einige von Euch kennen sicherlich die Asymptote aus der Mathematik, auch hierzu kann man Parallelen ziehen.

Private Sub HeapSort(ByVal n As Long)

    Dim t, v, i, j, k, l, m As Long
    
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    
    For i = 1 To n
        daten_sortiert(i) = daten(i)
    Next i
    
    m = n
    For l = n \ 2 To 1 Step -1
       k = l
       t = daten_sortiert(k)
       Do While k <= n \ 2
          j = k + k
          If j < n Then
             If daten_sortiert(j) < daten_sortiert(j + 1) Then j = j + 1
          End If
          If t >= daten_sortiert(j) Then Exit Do
          daten_sortiert(k) = daten_sortiert(j)
          k = j
       Loop
       daten_sortiert(k) = t
    Next l
    Do
       v = daten_sortiert(1)
       daten_sortiert(1) = daten_sortiert(m)
       daten_sortiert(m) = v
       m = m - 1
       k = 1
       t = daten_sortiert(k)
       Do While k <= m \ 2
          j = k + k
          If j < m Then
             If daten_sortiert(j) < daten_sortiert(j + 1) Then j = j + 1
          End If
          If t >= daten_sortiert(j) Then Exit Do
          daten_sortiert(k) = daten_sortiert(j)
          k = j
       Loop
       daten_sortiert(k) = t
    Loop Until m <= 1
    
    For i = 2 To n
        List2.AddItem daten_sortiert(i)
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 8

Heapsort hat eine relativ stabile Zeitbeanspruchung, somit ist das Verfahren recht berechenbar und gebräuchlich. Die Eigenschaften sind: iterativ, in-place, instabil, nicht parallelisierbar.

Die Theoretische Leistungsanalyse von Heapsort stellt für den Mathematiknormalverbraucher ein größeres Problem dar. Wir haben keine klar zu deutenden Hauptschleifen, die fest arbeiten, sonder wir haben k Knoten und mehrere Splits. Bei einer praktischen Leistungsanalyse kommen wir auf 77,610 ms .

Shellsort ist ein asymptotisch gutes Verfahren Da intern Insertsort (oder Bubblesort) verwendet wird, kann dieser Algorithmus gleichzeitig zur Gruppe der umhüllenden Sortieralgorithmen gezählt werden. Shellsort bietet den Vorteil, daß es trotz seiner Verwandtschaft zu den elementaren Sortieralgorithmen eine deutlich bessere Laufzeit besitzt. Hinzu kommt, daß es iterativ und ohne zusätzlichen Speicherplatz realisiert werden kann. Aufwand und Laufzeit halten sich somit, in einer optimalen Region. Hinzu kommt, dass er parallelisiert werden kann. Auch muss man sagen das Shellsort zu den instabilen Verfahren gehört. Hier spielt das ganze allerdings nur eine untergeordnete Rolle, weil wir nur mit Zahlenwerten Arbeiten, wobei wir die Vertauschung nicht bemerkt wird.
Der Name "Shellsort" kommt von D.L. Shell, (1959).

Private Sub shellsort(ByVal n As Long)
Dim i As Long, j As Long, delta As Long, elem As Long

    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    
    For i = 1 To n
        daten_sortiert(i) = daten(i)
    Next i
    
    delta = 1
    Do
       delta = 3 * delta + 1
    Loop Until delta > n
    Do
       delta = delta \ 3
       For i = delta + 1 To n
          elem = daten_sortiert(i)
          j = i
          Do While daten_sortiert(j - delta) > elem
             daten_sortiert(j) = daten_sortiert(j - delta)
             j = j - delta
             If j <= delta Then Exit Do
          Loop
          daten_sortiert(j) = elem
       Next i
    Loop Until delta = 1
   
    For i = 2 To n
        List2.AddItem daten_sortiert(i)
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 9

Da wir es hier mit sehr durchdachten Sortierverfahren zu tun haben, kann ich nur empfehlen, sich die angesprochenen Algorithmen noch einmal zu Gemüte zu führen. Hierzu ein kleiner Tipp: Der Debugger kann eine große Hilfe sein. Ich habe zu diesem Verfahren noch keine Theoretische Leistungsanalyse gefunden.

Bei einem Laufzeittest ergibt sich eine Zeitmessung von: 47,741 ms

Vergleichen wir diesen Wert mit den vorangegangen, so können wir eine deutliche Optimierung erkennen.

Quicksort gehört zur Gruppe der asymptotisch optimalen Sortieralgorithmen. Obwohl er im schlechtesten Fall keine besonders gute Laufzeit besitzt, kann diese im mittleren Fall als optimal angesehen werden. Quicksort ist nicht umsonst das bekannteste und am meisten angewendete Verfahren. Es ist relativ einfach, leicht zu implementieren und im mittleren Fall optimal. Allerdings gibt es keine zufriedenstellende iterative Realisierung und in bestimmten Fällen kann die Laufzeit deutlich schlechter ausfallen. Der Name "Quicksort" kommt von quick (dt. schnell) und spielt auf sein (in der Regel) phantastisches Laufzeitverhalten an.
Die Idee wurde erstmalig 1962 von Hoare vorgestellt.

Private Sub QuickSort(n As Long)
    Dim i As Long
    
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    
    For i = 1 To n
        daten_sortiert(i) = daten(i)
    Next i
    
    Call Quick_Sort(0, n, daten_sortiert())
    
    For i = 2 To n
        List2.AddItem daten_sortiert(i)
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Private Sub Quick_Sort(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
        If l < j Then Quick_Sort l, j, a()
        If i < r Then Quick_Sort i, r, a()
End Sub

Listing 10

Im Regelfall stell Quicksort den optimalsten Algorithmus dar. Die Theoretische Leistung beträgt hier für einen allgemeinen Algorithmus den Optimalwert: n logn. Ob man nun Quicksort verwendet, muss man selbst entscheiden.

Zeitmessungen ergeben bei einem unsortierten Feld: 37,462 ms

Kommen wir nun zum letzten Algorithmus für dieses Tutorial: Intersort. Die Idee ist beim Sonnen an einem See entstanden. Bis ich mich etwas schlau gemacht habe und das Verfahren Bucketsort fand. Da es nicht die volle Ähnlichkeit zu Bucketsort besitzt behalte ich den Namen Intersort bei. Das Programm funktioniert etwas anders als die vorangegangenen, stellt aber einen recht simples Schubladensystem dar. Für alle Werte die auftreten können ist eine Schublade vorgesehen. Tritt dieser Wert nun auf, so wird er einsortiert. Die einsortierten Werte werden nun noch aus der Schublade herausgeholt und ergeben die Endabnahme.

Private Sub intersort(ByVal n As Long)
    Dim i As Integer, Datensatz(10001) As Integer
    Dim Daten_satz(10001) As Integer, j As Integer
    
    xtime.Calibrieren
    xtime.Start
    List2.Visible = False
    List2.Clear
    
    For i = 1 To n
        Datensatz(daten(i)) = daten(i)
        Daten_satz(daten(i)) = Daten_satz(daten(i)) + 1
    Next i
    For i = 1 To n
        For j = 1 To Daten_satz(i)
            List2.AddItem Datensatz(i)
        Next j
    Next i
    
    List2.Visible = True
    xtime.Halt
    Text1.Text = "Zeitmessung: " & Format(xtime.RunTime, "0.000 ms")
End Sub

Listing 11

Dieses Verfahren hat aufgrund der, sehr wahrscheinlich, mehrfach auftretenden Werte eine, im theoretischen Teil auftretende, Operationenzahl von n * 2. Ich finde, dass kann sich sehen lassen. Könnten wir davon ausgehen, das wir keine Stabilisierung benötigen würden (Also: Werte treten nur einmal auf.), dann wäre die Theoretische Leistung = n. ...Unser Ziel.

Schauen wir uns nun die praktische Leistung an, so erhalten wir für n = 2000 11,582 ms
Intersort ist also einer der schnellsten, hier aufgeführten, Algorithmen.

Hier möchte ich noch einmal alle Zahlen geballt auflisten, um noch einmal die Effektivität der einzelnen Algorithmen zu bewerten. Der kursive Wert ist immer die schlechteste Zahl und der fett gedruckte Wert immer die beste Zahl in dem angegebenen Bereich. Die Werte die ich für n gewählt habe, sollen die sehr breite Leistungsspanne unserer Algorithmen möglichst vollständig abdecken. In der nun folgenden Tabelle, werden wir sehen wovon ich spreche.

Man erkennt deutlich wie leistungsstark Intersort gegenüber den anderen Algorithmen ist. Gerade der Vergleich von Intersort bei n = 10.000 und Allocationsort bei n = 500 Elementen. Auch Quick- und Shellsort können sich sehen lassen.

Nun kommt noch die Leistung der Verfahren bei bereits sortierten Datensätzen:

Vergleichen wir die Werte der Algorithmen bei bereits sortierten Datensätzen, so erhalten wir sehr stark variierende Werte. Zu Anfang erzielt Insertionsort die besten Werte, das liegt wohl in seiner Natur, denn das Verfahren selbst weist Testroutinen auf, um nicht zu sortieren. Anschließend zeigt Intersort die beste Optimierung. Bubble- und Allocationsort sortieren die Werte fast komplett neu und das ohne Notwendigkeit.

Ich hoffe, dass klar geworden ist wie Sortieralgorithmen aufgebaut sind und wie diese fundamentalen Dinge aus Sicht der Informatik optimiert werden können. Manchmal wundere ich mich selbst, wie viel man aus einem Verfahren zeitmäßig herausholen kann. Außerdem würde ich mich freuen, wenn sich ein paar meiner Leser ebenfalls für dieses Thema begeistern und vielleicht mal etwas durch den Kopf gehen lassen. Denn Optimierung und Arbeiten von und mit Programmen kann ein sehr spannendes Thema sein und ist alles andere als trocken. Es ist nämlich nicht die beste Lösung, auf immer schneller werdende Computer zu warten. In naher Zukunft plane ich ein 3. Teil dieses Themas, sowie die Übersetzung nach C++. Ich freue mich jetzt schon auf die Anregungen und Kritik der Leser.

Projekt als Download