Home
Writing
ETH

Quiz on Sorting Algorithms

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

MergeSort ist ein stabiler Sortieralgorithmus.

True False

MergeSort ist stabil, wenn beim Mergen bei gleichen Elementen zuerst das Element aus dem linken Teil genommen wird.

QuickSort mit zufälliger Pivotwahl hat eine erwartete Laufzeit von $O(n \log n)$.

True False

Mit zufälliger Pivotwahl ist die erwartete Laufzeit von QuickSort $O(n \log n)$, obwohl der Worst Case weiterhin $O(n^2)$ ist.

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