Jahrgangsstufe Q1 - Informatik - Donnerstag, der 15. April 2021


Rekursion

Mein Name:
Jahrgang/Klasse:
Meine E-Mail-Adresse:

Quicksort II

Der Algorithmus zur Erinnerung:

  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

Am Dienstag wurde bereits gezeigt, wie der Algorithmus auf dem Feld mit 8 2 1 7 7 5 3 arbeitet:

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

Auftrag 1:

Nach der rekursiven Teilung wird der linke Teil des Feldes erneut mit Quicksort bearbeitet. Zeige wie oben den weiteren Fortgang des Programmes für den linken Teil. Ergänze.
(Achtung: Bei der Berechnung des Index für das Pivot-Element handelt es sich um eine Ganzzahldivision. Z. B. ergibt dann (1 + 2)/2 = 1, weil der Rest bzw. die Nachkommastelle wegfallen.)

Auftrag 2:

Das Feld soll zufällig gefüllt werden. Es soll untersucht werden, ob sich bei Quicksort so wie bei Bubblesort und Minsort bei Verdopplung der Feldelementeanzahl die benötigte Zeit vervierfacht.