Quicksort Folge mit 9 Zahlen angeben

Question

Hi Leute, habe ein Problem mit dieser Aufgabe.

Geben Sie eine Folge mit 9 Zahlen an, welche mit nur 3 Vertauschungen durch Quicksort sortiert wird (Vertauschungen eines Elements mit sich selber ignorieren wir and dieser Stelle). Zeigen Sie, dass genau drei Vertauschungen gemacht werden und geben Sie dafür alle Zahlenpaare an, die der Algorithmus miteinander vergleicht bis die Folge sortiert ist (unabhängig davon, das der Algorithmus anschließend noch weitere Paare vergleicht).

Comments

Man muesste halt wissen, wie Quicksort funktioniert. Das als Tipp fuer Dich. Ausserdem gibt es zahlreiche Quicksort-Varianten. Man muesste wenigstens noch wissen, wie das Pivot-Element ausgewaehlt wird.

---

Hi, das Pivot-Element soll immer das letzte Element der Folge sein.

Answer 1

Entscheidend ist hier, wie der Pivot gewählt wird. Beim Quicksort gibt es unterschiedliche Implementierungen, das Pivot-Element kann entweder randomisiert erfolgen (der Quicksort hat die beste Laufzeit bei einem Pivot in der Mitte), oder das jeweils erst oder letzte Element ist der Pivot. Ohne das zu spezifizieren, ist die Frage daher eher schwer zu beantworten, du müsstest dich dann auf eine Variante festlegen.