• Midterm 1 Note

Sorting Algorithm

Comparison Sort

• Bubble Sort: $\Theta(n^2)$
• Selection Sort: $\Theta(n^2)$
• Insertion Sort: $\Omega(n),\,O(n^2)$
• Merge Sort: $\Theta(n\,lgn)$
• Heap Sort: $\Theta(n\,lgn)$
• Quick Sort: $\Omega(n\,lgn),\,O(n^2)$

Non-comparison Sort

• Counting Sort: $\Theta(n+k)$
• Radix Sort: $\Theta(d(n+k))$
• Bucket Sort: $\Omega(n),\,O(n^2)$
• Time Complexity Collection

BubbleSort

BubbleSort(A, n)       //  Θ(n^2)
for i = 1 to n-1
	for j = n downto i+1
		if A[j]<A[j-1]
			swap A[j] with A[j-1]

QuickSort

QuickSort(A, p, r)        //  Best case: Θ(nlgn)
if p < r                  //  Worst case: Θ(n^2)
	q = Partition(A, p, r)
	QuickSort(A, p, q-1)
	QuickSort(A, q+1, r)

Partition(A, p, r)        //  Θ(n)   
x = A[r]
i = p - 1
for j = p to r-1
	if A[j]<=x
		i = i + 1
		exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1

RandomizedQuicksort(A, p, r)    //  Expected: Θ(nlgn)
if p < r
	q = RandomizedPartition(A, p, r)
	RandomizedQuicksort(A, p, q-1)
	RandomizedQuicksort(A, q+1, r)

RandomizedPartition(A, p, r)    //  Θ(n)
i = Random(p, r)
exchange A[r] with A[i]
return Partition(A, p ,r)

CountingSort

// 0<=A[j]<=k, preserves the input order among equal elements
CountingSort(A, n, k)                //  Θ(n+k)
let B[1:n] and C[0:k] be new arrays
for i = 0 to k
	C[i] = 0
for j = 1 to n
	C[A[j]] = C[A[j]] + 1
for i = 1 to k
	C[i] = C[i] + C[i-1]
for j = n downto 1
	B[C[A[j]]] = A[j]
	C[A[j]] = C[A[j]] - 1
return B

BucketSort

// 0<=A[i]<=1
BucketSort(A, n) // All lines takes Θ(n) except the insertion sort
let B[0:n-1] be a new array     // Expected: Θ(n)
for i = 0 to n-1
	make B[i] an empty list
for i = 1 to n
	insert A[i] into list B[⌊n*A[i]⌋]
for i = 0 to n-1
	sort list B[i] with insertion sort
concatenate the list B[0], B[1],...,B[n-1] together in order
return the concatenated lists

RandomizedSelect

RandomizedSelect(A, p, r, i)     //  Expected: Θ(n)
if p == r
	return A[p]
q = RandomizedPartition(A, p, r)
k = q - p + 1
if i == k
	return A[p]
elseif i < k
	return RandomizedSelect(A, p, q-1, i)
else
	return RandomizedSelect(A, q+1, r, i-k)

Time Complexity

For recurrence relation $T(n)=a\,T(\frac{n}{b})+f(n)$, Master Method is a good way to calculate the time complexity of recursive algorithms.

Here: $a\,T(\frac{n}{b})=a'\,T(\lfloor\frac{n}{b}\rfloor)+a''\,T(\lceil\frac{n}{b}\rceil),\,a=a'+a''$

Case 1

$f(n)=O(n^{log_{b}a-\epsilon}),\epsilon>0~~~=>~~~T(n)=\Theta(n^{log_{b}a})$

Case 2