Quicksort I

Der berühmteste rekursive Algorithmus zum Sortieren ist Quicksort.

Auftrag 1:

Studiere die ersten beiden Abschnitte auf Seite 1 der PDF-Datei zum Problem.

Das Programm zur Lösung des Problems ist in rekursiver Formulierung erstaunlich kurz formuliert.

  void quicksort(int links, int rechts)
  { int nachlinks = rechts; // Laufindex, der vom rechten Ende nach links laeuft
    int nachrechts = links; // Laufindex, der vom linken Ende nach rechts laeuft
    if (nachrechts < nachlinks)
       { // Pivotelement bestimmen
         int pivot = feld[(nachrechts + nachlinks)/2];

         while (nachrechts <= nachlinks)
         {    // Links erstes Element suchen, das
              // groesser oder gleich dem Pivotelement ist
              while ((nachrechts < rechts) && (feld[nachrechts] < pivot))
                   nachrechts++;

              // Rechts erstes Element suchen, das
              // kleiner oder gleich dem Pivotelement ist
              while ((nachlinks > links) && (feld[nachlinks] > pivot))
                   nachlinks--;

              // Wenn nicht aneinander vorbei gelaufen, Inhalte vertauschen
              if (nachrechts <= nachlinks)
                   { vertausche(nachrechts, nachlinks);
                     nachrechts++;
                     nachlinks--;
                   }
         } // end while

         // Linken Teil sortieren
         if (nachlinks > links) quicksort (links, nachlinks);

         // Rechten Teil sortieren
         if (nachrechts < rechts) quicksort (nachrechts, rechts);

       } // end if
  }  // quicksort

Auftrag 2:

Wie in der obigen PDF-Datei angegeben soll zuerst ein Feld durch "Handarbeit" sortiert werden. Notiere jede Änderung der Indizes nachrechts und nachlinks und schreibe jeweils bei Vertauschung von Elementen die Folge neu auf. Zur Kontrolle ist das mit dem angegebenen Feld hier bis zur ersten rekursiven Teilung gemacht worden.

links = 0   rechts = 6   pivot = 7

8   2   1   7   9   5   3
nachrechts = 0     nachlinks = 6

3   2   1   7   9   5   8
nachrechts = 1     nachlinks = 5

nachrechts = 2     nachlinks = 5

nachrechts = 3     nachlinks = 5

3   2   1   5   9   7   8
nachrechts = 4     nachlinks = 4

nachrechts = 4     nachlinks = 3

Rekursive Teilung:
Linker Teil:             Rechter Teil:
3   2   1   5            9   7   8

Verfahre ebenso mit dem hier angegebenen Feld bis zur ersten rekursiven Teilung:

Auftrag 3:

In der Datei QuicksortDemo.zip ist ein direkt lauffähiges BlueJ-Projekt gespeichert. Entpacke die Dateien und starte das Programm. Vergleiche mit den Sortierverfahren vom 16.02.2021 und gib hier die mit Deinem Computer ermittelten Zeiten an..