[SOLVED] CS algorithm Sorting in O(n)

Sorting in O(n)
1

So far we have been looking at comparative sorts (where we only can compute < or >, but have no idea on range of numbers)
The minimum running time for this type of algorithm is (n lg n)
3
Sorting!

5
All n! permutations must be leaves
Worst case is tree height
Sorting!

A binary tree (either < or >) of height h has 2h leaves:
2h > n!
lg(2h) > lg(n!) (Stirlings approx) h > (n lg n)
6
Sorting!

Today we will make assumptions about the input sequence to get O(n) running time sorts
This is typically accomplished by knowing the range of numbers
7
Comparison sort

Sorting again! -Comparison sorting limits -Bucket sort
-Count sort
-Radix sort
8
Outline

1. Store in an array the number of times a number appears
2. Use above to find the last spot available for the number
3. Start from the last element, put it in the last spot (using 2.) decrease last spot array (2.)
9
Counting sort

A = input, B= output, C = count for j = 1 to A.length
C[ A[ j ]] = C[ A[ j ]] + 1
for i = 2 to k (range of numbers)
C[ i ] = C[ i ] + C [ i 1 ] for j = A.length to 1
B[ C[ A[ j ]]] = A[ j ]
C[ A[ j ]] = C[ A[ j ]] 1
13
Counting sort

k = 5 (numbers are 2-7) Sort: {2, 7, 4, 3, 6, 3, 6, 3}
1. Find number of times each number appears
C = {1, 3, 1, 0, 2, 1} 2, 3, 4, 5, 6, 7
14
Counting sort

Sort: {2, 7, 4, 3, 6, 3, 6, 3}
2. Change C to find last place of each element (first index is 1)
C = {1, 3, 1, 0, 2, 1}
{1, 4, 1, 0, 2, 1}
{1, 4, 5, 0, 2, 1}{1, 4, 5, 5, 7, 1} {1, 4, 5, 5, 2, 1}{1, 4, 5, 5, 7, 8}
15
Counting sort

Sort: {2, 7, 4, 3, 6, 3, 6, 3}
3. Go start to last, putting each element into the last spot avail.
C = {1, 4, 5, 5, 7, 8}, last in list = 3 234567
{ , , ,3, , , , }, C =
1 2 3 4 5 6 7 8 {1, 3, 5, 5, 7, 8}
16
Counting sort

Sort: {2, 7, 4, 3, 6, 3, 6, 3}
3. Go start to last, putting each element into the last spot avail.
C = {1, 4, 5, 5, 7, 8}, last in list = 6 234567
{ , , ,3, , ,6, }, C =
1 2 3 4 5 6 7 8 {1, 3, 5, 5, 6, 8}
17
Counting sort

Sort: {2, 7, 4, 3, 6, 3, 6, 3}
1 2 3 4 5 6 7 8 2,3,4,5,6,7 { , , ,3, , ,6, }, C={1,3,5,5,6,8} { , ,3,3, , ,6, }, C={1,2,5,5,6,8} { , ,3,3, ,6,6, }, C={1,2,5,5,5,8} { , 3,3,3, ,6,6, }, C={1,1,5,5,5,8} { , 3,3,3,4,6,6, }, C={1,1,4,5,5,8} { , 3,3,3,4,6,6,7}, C={1,1,4,5,5,7}
18
Counting sort

Run time?
19
Counting sort

Run time?
Loop over C once, A twice
k + 2n = O(n) as k a constant
20
Counting sort

Does counting sort work if you find the first spot to put a number in rather than the last spot?
If yes, write an algorithm for this in loose pseudo-code
If no, explain why
21
Counting sort

Sort: {2, 7, 4, 3, 6, 3, 6, 3}
C = {1,3,1,0,2,1} -> {1,4,5,5,7,8} instead C[ i ] = sumj