Week 10. Sorting Algorithms

Sorting

Sorting is a fundamental application for computers. It is one of the most intensively studied and important operations. An initial sort of data can significantly enhance the performance of algorithms.

A sorting algorithm is stable if the relative order of any two items with the same key in an input sequence is preserved after the execution of the algorithm.

Summary of Sorting Algorithms

Algorithm	Time	Notes
selection-sort	$O(n^2)$	in-place / slow
insertion-sort	$O(n^2)$	in-place / slow
quick-sort	$O(n\log n)$ expected	in-place / fastest
heap-sort	$O(n\log n)$	in-place / fast
merge-sort	$O(n\log n)$	sequential data access / fast

Merge Sort

Divide-and-Conquer

Divide-and-Conquer is a general algorithm design paradigm:

• Divide: divide the input data $S$ into two disjoint subsets $S_1$ and $S_2$
• Recur: solve the subproblems associated with $S_1$ and $S_2$
• Conquer: combine the solutions for $S_1$ and $S_2$ into a solution for $S$

Link to original

Merge Sort

Merge Sort on an input sequence $S$ with $n$ elements consists of three steps:

• Divide: if $S$ has zero or one element, return $S$. Otherwise, remove all elements from $S$ and put them in two sequences, $S_1$ and $S_2$, each containing about half of the elements of $S$. $S_1$ contains the first $\lceil \frac{n}{2}\rceil$ elements of $S$ and $S_2$ contains remaining $\lfloor \frac{n}{2}\rfloor$ items.
• Recur: recursively sort $S_1$ and $S_2$
• Conquer: merge $S_1$ and $S_2$ into a sorted sequence $S$

The base case for the recursion are subproblems of size $0$ or $1$.

Link to original

Tree Representation

Merge sort execution can be represented by the use of a Binary Tree.

• Each node represents a recursive call of merge-sort and stores:
  • Unsorted sequence before the execution + its partition
  • Sorted sequence at the end of the execution
• The root is the initial call
• The leaves are calls on sub-sequences of size $0$ and $1$

For example, sorting the sequence $(7,2,9,4)$:

Sorting the sequence $(7,2,9,4,3,8,6,1)$:

Performance

The height $h$ of the merge-sort tree is $O(\log n)$. At each recursive call, we divide the sequence is half.

• Amount of work that needs to be done at the nodes of each depth $i$ is $O(n)$.
• The tree has $2^i$ nodes at depth $i$.
• We partition and merge $2^i$ sequences of size $\frac{n}{2^i}$.
• Overall time spent at all the nodes at depth $i$ is $O(\frac{2^i\cdot n}{2^i})$ equivalent to $O(n)$.

Hence the total running time of merge-sort is $O(n\log n)$.

Quick Sort

Quick Sort is a randomised sorting algorithm based on Divide-and-Conquer but which favours a difficult division and easy conquer. We take the steps:

• Divide: If $S$ has at least two elements (otherwise stop):
  • Pick a random element $x$ (we call this the pivot)
  • Remove all the elements from $S$ and put into three sequences:
    • $L$: elements less than $x$
    • $E$: elements equal to $x$
    • $G$: elements greater than $x$
• Recur: sort $L$ and $G$
• Conquer: put the elements back in order into $S$ by inserting $L$, $E$, then $G$

It is common practice to choose the pivot to be the last element in $S$.

Partition

We partition an input sequence as follows:

• remove each element $y$ from $S$
• insert $y$ into $L$, $E$, or $G$ depending on the result of the comparison with pivot $x$

Each insertion and removal is at the beginning or at the end of a sequence, and hence takes $O(1)$ time. Thus, the partition step of quick-sort takes $O(n)$ time.

def partition(S, p):
	L, E, G = empty sequences
	x = S.remove(p)
	E.addLast(x)
	while not S.isEmpty():
		y = S.remove(S.first())
		if y < x:
			L.addLast(y)
		else if y = x:
			E.addLast(y)
		else:
			G.addLast(y)
 
	return L, E, G

Tree Representation

The execution of quick-sort can be represented by a Binary Tree.

• Each node represents a recursive call of quick-sort and stores:
  • Unsorted sequence before execution + pivot
  • Sorted sequence at the end of execution
• The root is the initial call
• Leaves are calls on sub-sequences of size $0$ or $1$

For example, sorting the sequence $(7,4,9,6,2)$, with pivot = $6$:

Sorting the sequence $(7,2,9,4,3,7,6,1)$:

Worst-case run time

The worst-case for quick-sort occurs when the selected pivot is the unique minimum or maximum element of the list.

• One of $L$ and $G$ has size $n-1$ and the other has size $0$.
• The running time is proportional to sum $n+(n-1)+\dots +2+1$.

Hence, worst-case running time of quick-sort is $O(n^2)$.

Expected run time

Consider a recursive call of quick-sort on a sequence of size $s$:

• Good call: the sizes of $L$ and $G$ are each less than $\frac{3}{4}s$
• Bad call: one of the sizes is greater than $\frac{3}{4}s$

A call is good with probability $\frac{1}{2}$.

We use a probabilistic fact: the expected number of coin tosses required in order to get $k$ heads is $2k$. For a node of depth $i$, we expect:

• $\frac{1}{2}i$ ancestors are good calls
• the size of the input sequence for the current call is at most ${\frac{3}{4}}^{\frac{i}{2}}n$

Therefore, we have:

• for a node of depth $2{\log }_{\frac{4}{3}}n$, the expected input size is one
• the expected height of the quick-sort tree is $O(\log n)$

The amount or work done at the nodes of the same depth is $O(n)$, Thus, the expected running time of quick-sort is $O(n\log n)$.

In-Place Quick Sort

Quick-sort can be implemented to run in-place. The divide step can be done without using any additional array:

• assume we want to divide $A[\text{left}-\text{right}]$ with respect to $A[\text{right}]$
• maintain two indices, $L$ (left cursor) and $R$ (right cursor) with initial values set to $\text{left}$ and $\text{right}$ respectively
• elements which have not been considered yet are in $A[(L+1)\dots (R+1)]$

Now, iterate until $L\ge R$:

• keep increasing $L$ by $1$ until an element $A[L]$ is larger than the pivot and $L\le R$
• keep decreasing $R$ by $1$ until an element $A[R]$ is smaller than pivot and $L\le R$
• if $L<R$, swap $A[L]$ and $A[R]$ and proceed to the next iteration

Finally, swap $A[L]$ and the pivot.

Bucket Sort

Bucket Sort

A bucket-sort does not use comparison. Let $S$ be a sequence of $n$ entries with keys in the range $[0,N-1]$.

Bucket-sort uses the keys as indices into an auxiliary array $B$ of sequences.

• Phase 1: empty sequence $S$ by moving each entry $(k,o)$ into its bucket $B[k]$
• Phase 2: for $i=0,\dots ,N-1$, move the entries of bucket $B[i]$ to the end of sequence $S$

Between the two phases, bucket sort takes $O(n+N)$ time:

• Phase 1 takes $O(n)$ time
• Phase 2 takes $O(N)$ time

Link to original

Sorting Lower Bound

Many sorting algorithms are comparison based. We can therefore derive a lower bound on the running time of any algorithm that uses comparisons to sort $n$ elements.

We can count all of the comparisons. Each possible run of the algorithm corresponds to a root-to-leaf path in a decision tree like so:

The height of the decision tree is a lower bound on the running time. Every input permutation must lead to a separate leaf output. Since there are $n!=1\cdot 2\cdot \dots \cdot n$ leaves, the height is at least $\log (n!)$.

Any comparison-based sorting algorithm takes at least $\log (n!)$ time. Therefore, any such algorithm takes at least:

$$\log (n!)\ge \log {\frac{n}{2}}^{\frac{n}{2}}=\frac{n}{2}\log \frac{n}{2}$$

That is, any comparison based sorting algorithm must run in $\Omega (n\log n)$ time.