Notes from CS2040S Week 3 Lecture 2 on Quick Sort

CS2040S_w3l2.md

CS2040S Week 3 Lecture 2

Notes from CS2040S Week 3 Lecture 2 on Quick Sort

Merge Sort

Bottom Up

Start with whole array. In the first pass, merge the pairs. Repeat.

15 7 9 2 6 12 13 4
7 15 2 9 12 6 4 13
2 7 9 15 4 6 12 13
2 4 6 7 9 12 13 15

Space Complexity

When Merge is called, a new array of size n is created.

if (n = 1) return // Theta(1)
else:
	X = mergesort() // S(n/2)
	Y = mergesort() // S(n/2)
	return merge(X, Y)

The recurrence relation is as follows:

S(n) = 2S(n/2) + n
S(n) = O(nlogn)

This can be derived by drawing out the recursion tree. There are logn levels where the total space requirements per level is n. So, the space complexity of Merge Sort is O(nlogn).

Better Space Usage

def mergesort(A, begin, end, temp)
	if (begin = end) return
	else:
		mid = begin + (end - begin)/2
		mergesort(A, begin, mid, temp)
		mergesort(A, mid+1, end, temp)
	merge(A[begin ... ned], A[mid + 1, end], temp)
	Copy(temp, A, begin, end) 

The new recurrence relationship is as follows:

S(n) = 2S(n/2) + 1
S(n) = O(n)

Though, the issue is the copying function is expensive. We can do better.

def mergesort(A, B, begin, end)
	if (begin = end) return
	else:
		mid = begin + (end - begin)/2
		mergesort(B, A, begin, mid)
		mergesort(B, A, mid+1, end)
	merge(A, B, begin, mid, end)

This has a space complexity of O(n).

Quick Sort

• Divide and Conquer
• Paranoid Quick Sort
• Randomized Analysis

Benefts

• Very fast
• Many optimisations
• In-place
• Good cache performance
• Good Parallelisation

if n = 1 return
else:
	p = partition(A[1...n], n)
	x = quicksort(A[1...p-1], p-1)
	y = quicksort(A[p+1, n], n-p)

All the smaller items are put to the left of the pivot and the larger items are placed to the right of the pivot.

• Divide: Partition the array into two sub arrays around a pivot x such that elements in lower subarray <= x <= elements in upper sub array
• Conquer: recursively sort the two sub arrays

Loop Invariants

• For every i < low: B[i] < pivot
• For every j > hi: B[j] > pivot
• A[high] > pivot at the end of each loop
  • Initially, true by assumption and prove it for each iteration

The runtime of partition is O(n).