Home
Writing
ETH

Quiz on Sorting Algorithms

← all Quizzes

Algorithmen und Datenstrukturen

Es existieren Arrays der Länge $n$, für die MergeSort Zeit $\Omega(n^2)$ benötigt.

True False

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

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.

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.

Welcher Algorithmus hat eine Laufzeit von $O(n \log n)$ auf dem Array $[n, n-1, \dots, 1]$ zum aufsteigenden Sortieren?

HeapSort BubbleSort InsertionSort SelectionSort

BubbleSort, InsertionSort und SelectionSort benötigen alle $\Theta(n^2)$ auf einem rückwärts sortierten Array. Nur HeapSort garantiert $O(n \log n)$.

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

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