3.3.8 Counting Sort

Knowledge Base > Algorithm > Sorting

Overview

Counting Sort sorts in linear time by first knowing the range of the numbers(e.g. k) in the array A , and creating an array C of this length k. Each index in C is used to count how many elements in A are less than i, and the counts stored in C can be used to put corresponding element in A into the right position in the output array.

Algorithm

Pseudocode

Counting-Sort(A)
 

1 for i ← 0 to k 2 do C[i] ← 0 3 for j ← 1 to length[A] 4 do C[A[j]] ← C[A[j]] + 1 5   ⊴ C[i] now contains the number of elements equal to i 6 for i ← 1 to k 7 do C[i] ← C[i] + C[i - 1] 8   ⊴ C[i] now contains the number of elements less than or equal to i 9 for j ← length[A] downto a 10 do B[C[A[j]]] ← A[j] 11       C[A[j]] ← C[A[j]] - 1

The procedure is as follow:

• Count the occurrence of an element i in A, and put in C, which means C[i] contains how many occurrence of element i in array A.
• Accumulate the counts, till C[i] contains the number of elements less or equal to i.
• Fill into output array B from backwards by putting each element i to count^th position in B, and each time decreasing counts of element i in C.

Time Complexity

Counting sort has a running time of Θ(n + k), where n is the number of elements to be sorted and k is the range of those numbers. If k = O(n), this algorithm has Θ(n) performance.

Space Complexity

Counting sort does not sort in place, since it creates two other arrays, counting array C and output array. The space complexity is Θ(n + k), where n and k are the length of the array A and C, respectively. No swap operations is performed during the process.

Stability

Counting sort is stable. However, if you change the last for loop statement, ascending from 0 to SIZE -1, the result would be NOT stable.

Source Code

• Counting Sort (C)