DAA HT23, Sorting

Let $A[1..n]$ be an array of $n$ distinct numbers. @Define an inversion of $A$.

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?

@State pseudocode for the quicksort algorithm, in terms of the $\text{Quicksort}$ function and the $\text{Partition}$ function.

@State pseudocode for the $\text{Partition}$ algorithm, which splits up an array $A[p:r]$ using $r$ as a pivot.

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?

The pseudocode for partitioning 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$

@State the pseudocode, in full.