Dein Fortschritt:
0 / 0 Aufgaben
1
Die Lagerverwaltung
14 BEAFB I–IIEine Lagerverwaltung sortiert die Lagerplatznummern offener Aufträge mit Quicksort (Quelltext aus dem Unterricht: quicksort(a, links, rechts) und zerlege(a, links, rechts) mit dem letzten Element als Pivot).
Reihung lager (Länge 7)
lager34018152273414255296
- Nennen Sie, was bei Quicksort den Schritten Teilen, Herrschen und Zusammenführen entspricht. (3 BE)
- Stellen Sie den Ablauf von
zerlege(lager, 0, 6)in einer Tracetabelle mit den Spaltenk,lager[k],lager[k] ≤ pivot,grenzeund Reihung dar. Geben Sie den Rückgabewert an. (5 BE) - Bestimmen Sie die beiden rekursiven Aufrufe nach dem ersten Zerlegen und die Gesamtzahl der Vergleiche
a[k] <= pivot, bislagersortiert ist. (3 BE) - Erklären Sie an einem selbst gewählten Beispiel mit vier Elementen, warum Quicksort nicht stabil ist. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Wo steckt die Arbeit, und was bleibt nach den rekursiven Aufrufen noch zu tun?
Hinweis zu Aufgabe b)
Das Pivot ist 29. Getauscht wird nur, wenn der Vergleich wahr ist.
Hinweis zu Aufgabe c)
Zerlegen eines Bereichs mit \(m\) Elementen kostet \(m - 1\) Vergleiche. Verfolgen Sie die Teilbereiche bis zur Größe 1 oder 0.
Hinweis zu Aufgabe d)
Nehmen Sie zwei gleiche Werte, markiert als 5a und 5b, und ein kleines Pivot am Ende.