Counting Sort

Counting sort, like Radix sort are linear time sorting algorithms. The performace of the sorting is proportional to the size of the interger keys being sorted.

Time Complexity

The worse case complexity of a linear algorithm like counting sort can be visualized using a decision tree. The decision tree represents all the permutations of the comparisons performed during a sort.

For example an array, array[n] where n=3, a decision tree would look like the following:

Counting sort decision tree where n=3, n is the number of elements in the array.

The height of the tree is the worse case running time (most comparisons).

We know that of the height of any decision tree is the worse case running time and that the decision tree must have at least n leaves (representing all permutations)…

Note that in the example of a binary decision tree (like this) there are only n leafs, each leaf representing a permutation. However other decision trees can represent +n leaves because of more than one possible outcome per element.

Psuedocode - unstable sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function countingSort(array) {
if (!array || array.length < 2) { return array; }
const countArray = [];
// O(k), k = max value of the array[n]
for (let a = 0; a < array.length; a++) {
countArray[array[a]] = countArray[array[a]] ? countArray[array[a]] + 1 : 1; // O(1)
}
const sorted = [];
// O(n+k)
for (let k = countArray.length - 1; 0 <= k; k--) {
for (let c = countArray[k]; 0 < c; c--) {
sorted.push(k);
}
}
return sorted;
}

(() => {
console.log(countingSort([4, 1, 3, 2, 16, 9, 10, 14, 8, 7])); // [16, 14, 10, 9, 8, 7, 4, 3, 2, 1]
console.log(countingSort([2, 5, 7, 4, 3, 8, 1, 6, 10, 9])); //[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
})();

Searching

From the decision tree example, we can derive the &‌Omega;(log n) as follows…

  1. We know that a height of a tree is O(log n). So sorting has…

height >= Omega(log n) (lower bound)

Sorting

When sorting an element of n, there are n! possible permutations and therefore n! possible comparisons…

1
2
3
height >= log n!
height = log (n . (n-1) . (n-2) ... 1)
= log(n) + log(n-1) + ... + log(n/2) + log(n/2 - 1) + ... + log(2) + log(1)

We know that in logerithmic scale, when we only look at n/2, these will make up most of the value. So we can say that the height is approximatlety …

n/2 approximation to help derive lower bound of log(n!).

1
2
3
4
5
6
7
height  >= Sum(log i), where i = n/2
>= log(n/2) + log(n/2) + ... + log(n/2) + log(n/2 - 1) + ... + log(2)
>= (n/2)log(n/2) + (n/2)log(2)
>= (n/2)(log(n) -log(2) + log(2))
= (n/2)log(n)
= 1/2(n)log(n)
==> O(nlog(n)

Remove all constant factors and we get n log (n)

Note you can also use Sterling approximation to show that log n! is n(log n).

Psuedocode - Stable sort

The above algorithm is not a stable sort since the relative positions are not maintained. This is demonstarted when you have two elements of the same value in the array to be sorted. The above algorithm does not guarantee the relative original order of those elements. For example [1, 2, 3, 2'], 2 and 2' might end up being sorted as [1, 2', 2,3] instead of what you would expected in a stable sort [1, 2, 2' ,3].

Below shows a summary of the above operations:

To modify the above counting sort algorithm into a stable sort algorithm, we do the following…

  1. Itterate through kArray to produce cArray (array that keeps the positions of values encountered in the unsorted array).

  2. Itterate through the unsorted array backwards, for each element lookup the position in cArray.

  3. Place the array in the position indicated in the cArray cArray[position], reduce cArray value by 1 so that the next encounter of the same value is placed adjacent in the sorted array.

Illustration of stable counting sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// console.log(countingSortStable([4, 1, 3, 4, 3])); // 1,3,3,4,4    
function countingSortStable(array) {
const kArray = [];
let max = array.length;
for (let a = 0; a <= max; a++) {
kArray[array[a]] = kArray[array[a]] ? kArray[array[a]] + 1 : 1;
if (!kArray[a])
kArray[a] = 0; // initialize inbetween itegers.

max = max > array[a] ? max : array[a]; // ensure max is biggest element array.
}
// kArray: [0,1,0,2,2]
const cArray = [];
for (let k = 0; k < kArray.length; k++) {
const curr = kArray[k] || 0;
const prev = cArray[k - 1] || 0;
cArray[k] = k > 0 ? curr + prev : 0;
}
// cArray: [0,1,1,3,5]
const sortedArray = [];
for (let a = array.length - 1; a >= 0; a--) {
const tmp = array[a];
const position = cArray[tmp];
sortedArray[position] = tmp;
cArray[tmp] -= 1;
}
// handle array[0] being undefined and showing up in the returned array as empty.
return sortedArray[0] === undefined ? sortedArray.splice(1, sortedArray.length) : sortedArray;
}

Searching - stable counting sort

Stable counting sort has the same searching as unstable counting sort. Since the algorithm doesn’t change how elements are searched.

Sorting - stable counting sort

We know from the algorithm that we are doing three itterations through arrays (kArray, cArray and sortedArray - kArray and sortedArray involves itterating through array[n]). So the time complexity for this would take at least:

O( n + k + n)

This is the same as:

O( 2n + k) or, removing constant factors … O(n+k).