DAA HT23, Sorting
Flashcards
Let $A[1..n]$ be an array of $n$ distinct numbers. What is an inversion of $A$?
A pair $(i, j)$ such that $i < j$ and $A[i] > A[j]$.
When proving that any comparison-based sorting algorithm runs in at most $\Theta(n \log n)$ time, you consider the decision tree with the leaves being possible permutations of a list of length $n$. How many leaves does this decision tree have?
When proving that any comparison-based sorting algorithm runs in at most $\Theta(n \log n)$ time, you know that the decision tree has at least $n!$ leaves. Therefore, what’s the depth of the tree and hence the worst-case number of comparisons in any sorting algorithm?
Quicksort
Program a worst-case $\Theta(n)$ sorting algorithm (not necessarily stable) that works under the assumption that all list entries are whole numbers less than some $k$.
Todo.