Counting Sort

Till now all the sorting algorithms we have seen so far were the comparison based sorting algorithms. Elements in the array were compared to one another to find their sorted position in the array.

Counting sort is a non-comparison based sorting algorithm. 

Algorithm:

Note: For simplicity, I'm not going to cover "stable" counting sort which preserves the order of equal keys in the input array. Refer to this link for stable counting sort.

The algorithm counts the number of times an element occurs in the array.

It makes an array, say count[], of size = highest value element+1

// given arr[] of n elements.

1.  Make an array count[] of size = (highest value in arr)+1
2.  initialise count[] with zeros.
3.  for i = 0 to n-1
4.      index = arr[i]
5.      count[index] = count[index] + 1
6.  k = 0
7.  for i = 0 to count.length-1
8.      for j = 1 to count[i]
9.          arr[k] = i
10.         k = k + 1

Example:

let arr = [3, 2, 1, 5, 2, 1]
max_value = 5
count = [0, 0, 0, 0, 0, 0]

// fill count array

1.  arr[0] = 3
    index = 3
    count[index] = count[index] + 1 = 1
    count = [0, 0, 0, 1, 0, 0]

2.  arr[1] = 2
    index = 2
    count[index] = count[index] + 1 = 1
    count = [0, 0, 1, 1, 0, 0]

3.  arr[2] = 1
    index = 1
    count[index] = count[index] + 1 = 1
    count = [0, 1, 1, 1, 0, 0]

4.  arr[3] = 5
    index = 5
    count[index] = count[index] + 1 = 1
    count = [0, 1, 1, 1, 0, 1]

5.  arr[4] = 2
    index = 2
    count[index] = count[index] + 1 = 1 + 1 = 2
    count = [0, 1, 2, 1, 0, 1]

6.  arr[5] = 1
    index = 1
    count[index] = count[index] + 1 = 1 + 1 = 2
    count = [0, 2, 2, 1, 0, 1]

Updated count = [0, 2, 2, 1, 0, 1]
      indexes =  0, 1, 2, 3, 4, 5

// fill the indexes in the array as many times as the value in count
fill 1 in arr twice arr = [1, 1]
fill 2 in arr twice arr = [1, 1, 2, 2]
fill 3 in arr once arr  = [1, 1, 2, 2, 3]
fill 5 in arr once arr  = [1, 1, 2, 2, 3, 5]

Sorted arr = [1, 1, 2, 2, 3, 5]

Code in Python:

# counting sort without stable sorting

# counting sort function
def counting_sort(arr):
    n = len(arr)

    # get the maximum value of the array
    max_val = max(arr)

    count = [0] * (max_val + 1)

    # fill the count array
    # for each element x in the array
    for x in arr:
        count[x] += 1

    k = 0
    for i in range(0, len(count)):
        for j in range(0, count[i]):
            arr[k] = i
            k += 1


arr = [3, 2, 1, 3, 2, 5, 5, 3]
print('Before counting sort:', arr)

# call counting sort function
counting_sort(arr)

print('After counting sort:', arr)

"""
Outputs:
Before counting sort: [3, 2, 1, 3, 2, 5, 5, 3]
After counting sort: [1, 2, 2, 3, 3, 3, 5, 5]
"""

Time Complexity:

If,

n = number of elements in the array

k = size of the count array or the largest value in the input array

for traversing the input array and count array:

time complexity = O(n+k) 

space complexity = O(k) for count array

For stable counting sort: GeeksForGeeks link

If you would like to understand how the stable counting sort works, leave a comment below. I'll write a post on it too. ;)

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal