Sorting

Input: an array of length \(n\): \(v[0,\cdots,n-1]\).

Output: a sorted array \(v\): \(v[i]\leq v[i+1]\forall 0\leq i<n-1\).

Recap Bubble Sort

Very BAD!

1. Input array.
2. Double nested for loop: Swap adjacent values when they are not in order.

Runtime: \(\Theta(n^2)\).

Recap Merge Sort

"Divide and Conquer" aka divide et impera

1. Divide the problem into subproblems.
2. Solve subproblems.
3. Combine solution of subproblem into solution.

Pseudocode omitted

Running time: \(T(n)=2T(n/2)+\Theta(n)\).

By Master Theorem, \(T(n)=\Theta(n\log n)\). One can guess the answer, and proof by induction

Exercise Counting Sort

1. Find the maximum value \(v\) of the input array.
2. Create a new counter array with length \(v\), and initialize to \(0\).
3. Scan the input array, increment on corresponding entry.
4. Scan the counter array, write on input array for counting times.

Running time: \(O(n+m)\) where \(m\) is the maximum value of the input array.

Simplified Master Theorem

If running time of a divide-and-conquer algorithm is \(T(n)=aT(n/b)+\Theta(n^k)\), if

• \(a>b^k,T(n)\in\Theta(n^{\log_b a})\).
• \(a=b^k,T(n)\in\Theta(n^k\log_b n)\).
• \(a<b^k,T(n)\in\Theta(n^k)\).