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
Can you give pseudocode for the quicksort algorithm, in terms of the $\text{Quicksort}$ function and the $\text{Partition}$ function?
QUICKSORT(A, p, r):
if p < r:
q = PARTITION(A, p, r)
QUICKSORT(A, p, q)
QUICKSORT(A, q+1, r)
PARTITION(A, p, r):
x = A[r]
i = p - 1
for j from p to r - 1:
if A[j] <= x:
i += 1
swap A[i], A[j]
swap A[i+1], A[r]
return i + 1
Can you give pseudocode for the $\text{Partition}$ algorithm, which splits up an array $A[p:r]$ using $r$ as a pivot?
PARTITION(A, p, r):
x = A[r]
i = p - 1
for j from p to r - 1:
if A[j] <= x:
i += 1
swap A[i], A[j]
swap A[i+1], A[r]
return i+1
What are the invariants for this code:
PARTITION(A, p, r):
x = A[r]
i = p - 1
for j from p to r - 1:
if A[j] <= x:
i += 1
swap A[i], A[j]
swap A[i+1], A[r]
return i+1
and what do they mean?
PARTITION(A, p, r):
x = A[r]
i = p - 1
for j from p to r - 1:
if A[j] <= x:
i += 1
swap A[i], A[j]
swap A[i+1], A[r]
return i+1
- if $p \le k \le i$ then $A[k] \le x$
- if $i+1 \le k \le j-1$ then $A[k] > x$
- if $k = r$, then $A[k] = x$
Saying that the array is divided into three sections
The pseudocode for paritioning an array $A[p, r)$ uses three variables, $x$, which stores the value of the pivot, $i$, which stores the index for the “low side” of the array, and $j$, which iterates over the array. Given that the invariants are
- if $p \le k \le i$ then $A[k] \le x$
- if $i+1 \le k \le j-1$ then $A[k] > x$
- if $k = r$, then $A[k] = x$
What’s the pseudocode, in full?
PARTITION(A, p, r):
x = A[r]
i = p - 1
for j from p to r - 1:
if A[j] <= x:
i += 1
swap A[i], A[j]
swap A[i+1], A[r]
return i+1
Proofs
Prove that any comparison-based sorting algorithm runs in at most $\Theta(n \log n)$ time.
Todo.
Programming
Program a worst-case $\Theta(n \log n)$ algorithm for finding the number of inversions (pairs $(i, j)$ such that $i < j$ and $A[i] > A[j]$) in an array.
Todo.
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.