Home
Writing
ETH

Quiz on Sorting Algorithms

HeapSort benötigt höchstens $O(n \log n)$ Zeit, um ein beliebiges Array der Länge $n$ zu sortieren.

True False

HeapSort hat eine garantierte Worst-Case-Laufzeit von $O(n \log n)$.

Für welches Array läuft InsertionSort in $\Omega(n^2)$?

$[2, 1, 3, 4, \dots, n]$ $[n, n-1, \dots, 1]$ $[1, 2, 3, \dots, n]$ Keines der genannten

Option (a) ist fast sortiert und benötigt $O(n)$. Ein rückwärts sortiertes Array ist der Worst Case für InsertionSort, da jedes Element alle vorherigen Elemente verschieben muss.

Nach $k$ Vergleichen von SelectionSort auf einem Array der Länge $n$ sind die ersten $O(\sqrt{k})$ Elemente garantiert sortiert.

True False

SelectionSort findet das Minimum des verbleibenden unsortierten Teils. Um das 1. Minimum zu finden, benötigt es $n-1$ Vergleiche. $k$ Vergleiche reichen möglicherweise nicht einmal für den ersten Durchlauf, wenn $k < n-1$.

Die Laufzeit von MergeSort auf der Eingabe $[1, 2, \dots, n]$ ist $\Theta(n)$.

True False

MergeSort teilt das Array immer rekursiv und benötigt $\Theta(n \log n)$, unabhängig von der Eingabereihenfolge.

Auf dem Array $[n, n-1, \dots, 1]$ beträgt die Laufzeit von QuickSort $O(n \log n)$, wenn das Pivot immer das erste Element ist.

True False

Mit dem ersten Element ($n$) als Pivot wird das Array in $[n-1, \dots, 1]$ und leer partitioniert. Dies führt zu einem Worst-Case-Verhalten von $O(n^2)$.

Quiz on Sorting Algorithms

Recent posts

Lecture Notes

Quizzes

New Siri needs that Steve Jobs touch

Conversations don’t flow linearly, so LLM interfaces shouldn’t either

LaTeX Collection