Home
Writing
ETH

Quiz on Sorting Algorithms

Bezüglich BubbleSort: Welche Aussage ist korrekt?

Nach $j$ Iterationen sind die größten $j$ Elemente am richtigen Platz Nach $j$ Iterationen sind die ersten $j$ Elemente sortiert Nach $j$ Iterationen sind die kleinsten $j$ Elemente am richtigen Platz Nach $j$ Iterationen ist das Array vollständig sortiert

BubbleSort 'bubbelt' das maximale Element in jedem Durchlauf ans Ende. Nach $j$ Durchläufen sind die letzten $j$ Elemente (die größten) sortiert.

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.

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

Es existiert ein Algorithmus mit Laufzeit $O(n)$, der eine Folge von $n$ Bits (0en und 1en) sortiert.

True False

Counting Sort oder Radix Sort können Bits in $O(n)$ Zeit sortieren.

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

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