Counting Sort Algorithm
A non in-place sorting algorithm that sorts the elements of an array by counting the frequency of each unique element. An auxiliary array is required to maintain those counts. Then using those counts to compute every element’s position in the final sorted array. Counting sort is an efficient algorithm that runs in O(n + k) time (n is the number of elements in the array; k is the range of values to be sorted). If the range of input array(ie. k) is very large, this algorithm requires a lot of space and becomes inefficient.
Table of Contents· How Does Counting Sort Algorithm Work?
∘ Auxiliary array — counts
∘ Build up the sorted array
∘ 1. rearrange array using simple counts
∘ 2. generate a sorted array using cumulative counts
∘ Counting sort for negative numbers
· Graphical Explanation
· 1. Positive array
∘ Rearrange array using simple counts
∘ Generate a sorted array using cumulative counts
· 2. Array contains negative values
∘ Generate a sorted array using cumulative counts
· Code Implementation
∘ Complexity
∘ Pseudocode
∘ Golang
∘ Python
How Does Counting Sort Algorithm Work?
Counting sort algorithm sorts the elements of an array by counting the number of times each element appears and assign it into an auxiliary array. We can fetch those counts to build up the final sorted output.
Auxiliary array — counts
Map elements in the input array to counts array indices.
We can retrieve the frequency of an element by counts[element].
Build up the sorted array
1. rearrange array using simple counts
Iterate through the counts array and fill up the elements to the array in order.
The simplified version of counting sort is easy to implement and understand. However, it only works for numbers. Numbers are indistinguishable, so stability is not an issue. If we use this simple way to handle non-numeric elements, the output will be not stable.
A stable sorting algorithm keeps the same order of equal elements/keys in the sorted output as they appear in the given input.
For stability sake, we need to use cumulative counts in counting sort.
2. generate a sorted array using cumulative counts
position(1-based), index(0-based), position = index + 1
By calculating the running sum of counts array(counts[i] += counts[i-1]), it indicates the position of the last elements in the sorted output. According to cumulative counts, it shows that the number of elements smaller than or equal to element i for each input element i. For example, counts[8] = 6 represents six elements are smaller or equal to element 8. Therefore, the last element of 8 must be assigned to the sixth position in the sorted output.
This information helps to place elements in the right location in the sorted output.
Now we can determine the position of the last elements from the cumulative counts. To complete the sorting, we iterate the input array in the reversed order and put elements to the current position in the sorted output. Then we decrement the corresponding value in the cumulative counts by 1 which is the position for the equal elements/keys to be placed. Because we scan backward, the order of the equal element/keys will be maintained in the sorted output. It is stable.
Counting sort for negative numbers
We have known that counting sort maps array values to the indices of the counts/auxiliary array. However, negative numbers map to negative indices will not work properly. Therefore, we need an offset to allow to map the negative elements to the counts indices.
offset = 0 - minValueOffset is calculated by 0 subtract the minimum number to be sorted. Now this minimum number is counted at index 0.
Let’s say, the minimum number to be sorted is -2, so the offset is 2(0–2=2). An element with value of 5 is counted at the index 7(element + offset = 5 + 2).
With above fine tune, we can apply counting sort on negative numbers.
Graphical Explanation
1. Positive array
Rearrange array using simple counts
- step1.a: get the maximum value to be sorted in the array
- step1.b: initialize an auxiliary array to store the frequency of each element. (set all values to 0)
- step2: count the frequency of each element of the array
- step3: rearrange the array to a sorted version
Generate a sorted array using cumulative counts
- step1.a: get the maximum value to be sorted in the array
- step1.b: initialize two auxiliary arrays.(set all values to 0)
- counts: store the frequency of each element
- sortedArray: store the final sorted array - step2: count the frequency of each element of the array
- step3: compute the cumulative sum of the count array
counts[i] += counts[i-1]- step4: Build up sorted array by iterating backward through the array
4.1: place the element at the final position
4.2: decrement the corresponding value in counts by 1
2. Array contains negative values
Generate a sorted array using cumulative counts
- step1.a: get the maximum and minimum value to be sorted in the array
- step.b: calculate offset
offset = 0 - minValue- step1.c: initialize two auxiliary arrays.(set all values to 0)
- counts: store the frequency of each element
- sortedArray: store the final sorted array - step2: count the frequency of each element of the array
- step3: compute the cumulative sum of the count array
counts[i] += counts[i-1]- step4: Build up sorted array by iterating backward through the array
4.1: place the element at the final position
4.2: decrement the corresponding value in counts by 1
Code Implementation
Complexity
Time: O(n + k)
Space: O(n + k)
n: the total number of elements in the input array
k: the range of elements to be sorted
Pseudocode
- Positive array
# find the input range
maxValue = max(array)# initialize auxiliary arrays and set all elements to 0
counts with length of (1+maxValue)
storedArray with length of array# count the frequency of every elements
for i from 0 to len(array):
element = array[i]
counts[element] += 1# calculate cumulative counts
for i from 1 to len(counts):
counts[i] += counts[i-1]# build up the sorted array
for i from len(array) to 0: # iterate backward
# place element to final position
element = array[i]
position = counts[element]
sortedIdx = position -1
sortArray[sortedIdx] = element
# decrement corresponding value by 1
counts[element] -= 1
- Array contains negative values
# find the input range
maxValue = max(array)
minValue = min(array)# calculate the offset
offset = 0 - minVlaue# initialize auxiliary arrays and set all elements to 0
counts with length of (1+maxValue+offset)
storedArray with length of array# count the frequency of every elements
for i from 0 to len(array):
element = array[i]
counts[element+offset] += 1# calculate cumulative counts
for i from 1 to len(counts):
counts[i] += counts[i-1]# build up the sorted array
for i in from len(array) to 0: # iterate backward
# place element to final position
element = array[i]
position = counts[element+offest]
sortedIdx = position -1
sortArray[sortedIdx] = element
# decrement corresponding value by 1
counts[element+offset] -= 1
Golang
- Positive array
- Array contains negative values
Python
- Positive array
- Array contains negative values
You can access the source code here.
Other sorting algorithms:
- Bubble sort algorithm
- Insertion sort algorithm
- Selection sort algorithm
- Quick sort algorithm
- Heap sort algorithm
- Merge sort algorithm
- Bucket sort algorithm
- Radix sort algorithm
- Sorting algorithms summary
