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!) (Stirling’s 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
Reviews
There are no reviews yet.