Jan 9. Sorting

QUICK-SORT

Input: Let A be the list to be sorted.

Algorithm: Pick a pivot element p \in A; let A_1 = (a \mid a\in A, a \le p) and A_2 = (a \mid a \in A, a > p). Recursively compute B_1 = QUICKSORT(A_1) and B_2 = QUICKSORT(A_2). Output (B_1, p, B_2).

Correctness: By induction on the size of the list to be sorted. The base case is when |A|=1 in which case correctness is obvious. The inductive step follows by observing that |B_1|, |B_2| < |A|.

Running Time: In the worst case quick sort takes \frac{n(n-1)}{2}, e.g., when the original list is already sorted and we take the pivot to be the first element at every step. This is because in the i^{th} step we have |A|=n-i+1 while |A_1|=0, |A_2|=n-i and so the total running time is \sum_{i=1}^n n-i = \frac{n(n-1)}{2}. Observe that the running time can never exceed \frac{n(n-1)}{2}. This is because there are \frac{n(n-1)}{2} unique pair-wise comparisons that can be made on elements of A and the only comparison made at any step is with the pivot element, hence no comparison is ever repeated (since the pivot is discarded in the subsequent recursive calls to QUICKSORT).

Improving the choice of pivot: If the two parts A_1 and A_2 are of equal size, then the total running time is O(n \log{n}). Let T(n) represent the time QUICKSORT takes on a list of size n. Then we get T(n) = 2 T(n/2) + O(n).

The idea is to pick a random pivot element p: later in the course, we will see that with good probability the two partitions will be approximately balanced, leading to an overall running time of O(n \log n).

MERGE-SORT

Input: Let A be the list to be sorted.

Algorithm: Partition the list into two equal size parts A_1, A_2 and let B_1 = MERGESORT(A_1) and B_2 = MERGESORT(A_2) be computed recursively. Then output MERGE(B_1,B_2), which merges these two sorted lists in linear time.

MERGE(B_1, B_2):

  • If |B_1| = 0 return B_2
  • Else if |B_2| = 0  return B_1
  • Else if B_1[0] \le B_2[0] return (B_1[0], MERGE(B_1 \setminus B_1[0], B_2))
  • Else return (B_2[0], MERGE(B_1, B_2 \setminus B_2[0])).

Correctness: By induction on the size of the list. The base case is when |A| = 1, in which case correctness is trivial. Since |B_1|, |B_2| < |A| they are correctly sorted by the inductive hypothesis and MERGE correctly merges two sorted lists into a single sorted list.

Running Time: Note that MERGE(B_1, B_2) takes time linear in |B_1|+|B_2|. Thus if T(n) is the time it takes to merge-sort a list of n numbers, then we get the following recurrence relation: T(n) = 2T(\frac{n}{2}) + O(n), which implies T(n) = O(n\log{n}).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s