Counting Sort
Objectives
We would like to :- Examine counting sort
Notes
- Counting sort is a non-comparsion based sort that trades space for speed.
- It is restricted to integers, and better for a small range of values.
- However, we might be sorting an array of records, somehow identified by a key.
- In the next algorithm, I will assume min = 0
- This is not required, but I don't want to carray key-min throughout the computation.
-
COUNTING-SORT(A) Input: an array indexed from 0 to A.size-1 The key element is a small integer. Output: The original array ordered- min ← min(A.keys)
- max ← max(A.keys)
- count ← array with max-min elements initialzed to 0
- for i ← 0 to A.size-1
- pos ← A[i].key
- count[pos] ← count[pos] + 1
- for i ← 1 to max
- count[i] ← count[i] + count[i-1]
- Allocate an array B of size A.size
- for i ← A.size-1 to 1
- pos ← A[i].key
- B[count[pos]] ← A[i]
- count[pos] ← count[pos] - 1
- return B
- Start by finding the min, max and range of the keys.
- Then create a counting array for the keys.
- In my implmenetation I made the key 5 - 15 just to make indexing fun.
- First loop (4-6), calculate the counts for each of the keys
- The second loop (7-8), computes the offsets for the end of each range.
- Ie if there are two of the first key, it's value is 2
- And if the second key has three values, the offset is 2+3
- But we are off by one, as we use 0 based indexing not 1
- So the first element (2) will go in positions 0 and 1,
- The second element (5) will go in positions 2,3,4
- The third loop (8-12) moves the elments from the array
into their position in the final array.
- Note, this preserves the order of any elements with the same key
- This is called a stable sort.
- I believe that this works.
- I belive it is O(max(n,k)), where k is the range of keys
- And it has space coplexity of O(n+k)