3.1 Direkte Sortiermethoden
3.2 Das Effizienz-Problem
3.3 Quicksort

3.1 Direkte Sortiermethoden

Wir vergleichen a[0] mit a[1]; wenn a[0] > a[1] ist, dann werden die beiden Zahlen ausgetauscht;
wir vergleichen a[0] mit a[2]; wenn a[0] > a[2] ist, dann werden die beiden Zahlen ausgetauscht;
wir vergleichen a[0] mit a[3]; wenn a[0] > a[3] ist, dann werden die beiden Zahlen ausgetauscht;
..... (usw bis) .....
wir vergleichen a[0] mit a[15]; wenn a[0] > a[15] ist, dann werden die beiden Zahlen ausgetauscht.

Wir vergleichen a[1] mit a[2]; wenn a[1] > a[2] ist, dann werden die beiden Zahlen ausgetauscht;
wir vergleichen a[1] mit a[3]; wenn a[1] > a[3] ist, dann werden die beiden Zahlen ausgetauscht;
..... (usw bis) .....
wir vergleichen a[1] mit a[15]; wenn a[1] > a[15] ist, dann werden die beiden Zahlen ausgetauscht.

Aufgaben:

1. Sortieren durch direkten Austausch:
   
   Schreiben Sie ein Programm, das mit Hilfe des oben beschriebenen Algorithmus ein mit 16 zufälligen Integerzahlen gefülltes Array aufsteigend sortiert.
   
   

   In Delphi stellen Sie dazu zunächst eine entsprechende Integer-Array-Variable zur Verfügung, die im ganzen Programm bekannt ist: deklarieren Sie sie daher im private-Abschnitt der Formular-Deklaration. Den Inhalt des Array können Sie dann mit Hilfe einer Prozedur (z.B. "ZeigeTabelle()") in einer StringGrid-Komponente darstellen lassen. Sorgen Sie beim Programmstart für eine entsprechende Beschriftung des StringGrid sowie für die Füllung des Arrays mit Zufallszahlen (zwischen 0 und 100) und deren Anzeige. Für die Details des Umganges mit der nicht ganz einfach zu handhabenden Komponente "StringGrid" sollten Sie die Delphi-Hilfe zu Rate ziehen. Nahezu alle relevanten Einstellungen lassen sich über die im Objekt-Inspektor aufgeführten Eigenschaften einstellen. Zur Implementierung des Sortierungsalgorithmus ist es sinnvoll, eine Prozedur "tausche()" zur Verfügung zu stellen, die zwei übergebene Integerzahlen vertauscht. Dabei gibt es 2 Möglichkeiten für die Parameter: entweder Sie übergeben direkt die Zahlen oder Sie übergeben nur die Indizes der Zahlen im Array. Welche der Möglichkeiten Sie wählen, hat einen gravierenden Einfluß auf die nötige Parameterliste der Prozedur! Warum? Außerdem ist es im Hinblick auf spätere Untersuchungen der verschiedenen Sortieralgorithmen sinnvoll, auch den Vergleich zweier Array-Einträge auszulagern, und zwar in eine boolsche Funktion "vergleiche()" (oder auch "istGroesser()"). Auch hier haben Sie wieder die beiden obengenannten Möglichkeiten für die Wahl des Parameter-Designs. Diesmal ist die Sache aber nicht so kritisch. Warum?

   In Java stellen Sie dazu zunächst eine entsprechende Integer-Array-Variable zur Verfügung, in der dann der eigentliche Sortiervorgang stattfinden wird. Diese Variable sollte auf derselben logischen Ebene deklariert werden wie die visuellen Komponenten Ihres Formulars, damit sie nämlich (genau wie diese) im gesamten Programm bekannt ist. Den Inhalt dieses Arrays können Sie dann mit Hilfe einer Prozedur (z.B. "moveIntsFromArrayToTable()" ) in einer Zeile einer jTable-Komponente darstellen lassen. Mit der Eigenschaft jTable.Columns können Sie schon zur Programmierzeit für passende Spaltenüberschriften sorgen: tragen Sie dort die Spalten-Nummern (0..15) ein. Wenn Sie die Eigenschaft RowCount auf "2" setzen, dann zeigt die Vorschau des JAVA-Editors zwar unter der Kopfzeile fälschlicherweise nur eine(!) Datenzeile an; zur Laufzeit werden Sie aber neben der Kopfzeile (mit dem Index "0" und den eingetragenen Spalten-Nummern) zwei(!) zunächst leere Datenzeilen (mit den Indizes "1" und "2") vorfinden. Schreibenden Zugriff auf die Datenfelder der Tabelle gestattet Ihnen die Methode "jTable.setValueAt(String data, int x, int y)". Beachten Sie, dass die Tabelle nur Strings darstellen kann! Zur Implementierung des Sortier-Algorithmus ist es sinnvoll, eine Prozedur "switchData()" zur Verfügung zu stellen, die zwei übergebene Integerzahlen vertauscht. Dabei ist es sinnvoll, dieser Prozedur die Array-Indizes der beiden zu vergleichenden Zahlen zu übergeben. Außerdem ist es im Hinblick auf spätere Untersuchungen der verschiedenen Sortieralgorithmen sinnvoll, auch den Vergleich zweier Array-Einträge auszulagern, und zwar in eine boolsche Funktion "compareData()", der ebenfalls die Array-Indizes der zu vergleichenden Daten übergeben werden.

   
   Die eigentliche Sortierprozedur kann dann als Klick-Prozedur eines entsprechenden Knopfes formuliert werden. Sehen Sie zusätzlich auch noch einen Knopf zum erneuten Befüllen des Array mit "frischen" Zufallszahlen vor!
   
   Für die weiteren Forschungen sollten sie das Programm mitzählen lassen, wie viele Vergleiche und wieviele Tauschvorgänge durchgeführt werden mussten, und diese Anzahlen nach dem Sortieren ausgeben lassen.
   
   
   
2. Bubble-Sort ist schon ein bisschen besser:


Verfolgt man beim Austausch-Sortieren den Weg einer bestimmten Zahl, dann fällt auf, dass manche Zahl von einer "schon ganz guten" Position wieder weit weg transportiert wird. Dieser Nachteil des Sortieralgorithmus kann gemildert werden, wenn man die innere der beiden Schleifen in Richtung fallender Indizes durchlaufen lässt, also zuerst mit dem letzten Element vergleicht, dann mit dem vorletzten usw. Diese Sortiermethode ist unter dem Namen "Bubble-Sort" bekannt.

Erweitern Sie Ihr Programm um eine entsprechende zweite Sortiermethode! Lassen Sie auch hier die Anzahl der Vergleiche und der Tauschvorgaänge während eines Sortierlaufs mitzählen.



3. Bewusst Auswählen hilft noch mehr:
   
   Man kann beim Sortieren durch Austausch viele Tauschoperationen einsparen, indem man erst dann tauscht, wenn man das kleinste der Elemente des Arrays gefunden hat. Die Grundidee dieses "Auswahl-Sort" genannten Algorithmus ist:
   
   
   Man suche das kleinste Element des ganzen Arrays und setze es (falls noch nötig) an den Anfang.
   Dann behandle man das Teilarray, das man erhält, wenn man das erste (kleinste!) Element wegläßt, auf eben dieselbe Weise.
   
   Beachten Sie, dass also der erste Tauschvorgang erst durchgeführt wird, nachdem das kleinste Element des (Teil-)Arrays gefunden wurde!
   
   Implementieren Sie in Ihrem Sortier-Programm einen solchen "Auswahl-Sort" als dritte Sortiermethode. Und lassen Sie auch hier wieder die Anzahl der Vergleiche und der Tauschvorgänge während eines Sortierlaufs mitzählen.
   
   
   [Gesamt-Lösungsvorschlag für die Aufgaben 1 bis 3] [Delphi] [Java]
   
   
   

3.2 Das Effizienz-Problem

Aufgabe:

4. Wettlauf der Algorithmen
   
   Untersuchen Sie die Leistungsfähigkeit der drei oben implementierten Sortier-Algorithmen, indem Sie eine Serie von Sortieraufgaben erledigen und dabei die Anzahl v der Vergleiche und die Anzahl t der Tauschoperationen protokollieren. Berechnen Sie dann für jeden Algorithmus einen mittleren Wert dieser Anzahlen.
   Untersuchen Sie nun, wie sich diese Kennzahlen verändern, wenn sich die Länge n des zu sortierenden Arrays ändert. Führen Sie dazu die eben beschriebene Versuchsserie nochmals mit Arrays des Doppelten bzw. des Zehnfachen der ursprünglichen Länge durch. Können Sie als Ergebnis Ihrer Untersuchungen für jede dieser Kennzahlen eine Formel v(n) bzw. t(n) angeben, die die Abhängigkeit von der Array-Länge n zeigt?
   (Falls Sie als Ergebnis der ersten drei Aufgaben kein geeignetes eigenes Programm zur Verfügung haben, oder Sie es in der Java-Variante nicht schaffen, die jTable-Komponente neu zu dimensionieren, dann können Sie die Experimente auch mit diesem Programm durchführen...)
   
   

3.3 Quicksort

   procedure QuickSort;

     procedure qs(li, re: Integer);
       var i, j, v: Integer;
       begin
       i := li; j := re;
       v := data[(li+re) Div 2];
       Repeat
         While IsLessThan(data[i], v) do
           i := i + 1;
         While IsLessThan(v, data[j]) do
           j := j - 1;
         If i <= j then begin
           Exchange(data[i], data[j]);
           i := i + 1;
           j := j - 1;
           end;
       until i > j;
       If li < j then qs(li, j);
       If i < re then qs(i, re);
       end;

     begin
     qs(0, Pred(max));
     end;

   public void QuickSort {
     qs(0, Pred(max));
   }

   private void qs(int li, int re) {
     int i = li;
     int j = re;
     int v = data[(li+re) / 2];
     do {
       while (isLessThan(data[i], v)) {
         i = i + 1;
       }
       while (isLessThan(v, data[j])) {
         j = j - 1;
       }
       if (i <= j) {
         switchData(i, j);
         i = i + 1;
         j = j - 1;
       }
     } while (i ≤ j);
     if (li < j) { qs(li, j) };
     if (i < re) { qs(i, re) };
   }

Aufgaben:

5. Das Arbeitspferd des Sortier-Alltags: Quick-Sort
   
   Implementieren Sie mit Hilfe des oben aufgeführten Quelltextes in Ihrem Sortier-Programm einen Quick-Sort als zusätzliche vierte Sortiermethode.
   Zählen Sie auch hier die Anzahl der Vergleiche und die Anzahl der Tauschaktionen.
   
   [Lösungsvorschlag] [Delphi] [Java]
   
   
   
6. Abschluss-Test "Jeder gegen jeden"
   
   Führen Sie den oben angegebenen Vergleichstest der Sortieralgorithmen nun auch noch für den Quick-Sort durch. (Falls Sie als Ergebnis der vorigen Aufgabe kein geeignetes eigenes Programm zur Verfügung haben, können Sie dieses nehmen.)
   
   Die für Quick-Sort gültigen Formeln für v(n) und t(n) sind von der Form k*n*log(n). Bestimmen Sie mit Hilfe Ihrer Messergebnisse die jeweils passenden Werte für die Konstante k.