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
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.)
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.