Photo by CHUTTERSNAP on Unsplash

Counting Sort & Radix Sort

In this blog, we will go through the two most common non-comparison-based sorting algorithms. But before we do that, why do we need non-comparison sorting?

Comparison-based sorting algorithms have a lower bound of O(nlogn) operations to sort n elements. This comes from the fact that a sorted array is one of the n! permutations that we can arrange the n numbers. Every time we do a comparison we actually reduce the number of permutation for arranging n numbers to half. To find the actual arrangement we need to do at least log2N! . To improve upon this lower bound we use non-comparison-based sorting algorithms like Counting & Radix sort. Both of these sorting algorithms (Count & Radix) sort the data in O(n)operations. They do so by making certain assumptions about data. These assumptions enable them to do sorting without actually doing comparisons on the elements themselves.

Counting Sort

Counting sort is a linear time sorting algorithm that sorts the data in O(n+k) time when elements are in the fix range k which is equal to lower_bound -upper_bound. For example for an array generated like the below one:

import random
randomlist = [random.randint(5,12) for i in range(20)]
print(randomlist)
[11,11,7,9,9,12,11,10,11,9,12,7,11,9,7,8,11,11,6,10]

We will have an array of size (12–5+1). Where 0th index represents item with value 5, 1st index represents item with value 6, 2nd with 7 and so on to 7th with 12.

def countSort(array):
    lower_bound , upper_bound = min(array), max(array)
    counter_array = [0]*(upper_bound-lower_bound+1)
    for item in array:
        counter_array[item-lower_bound] += 1
    pos = 0
    for idx, item in enumerate(counter_array):
        num = idx + lower_bound
        for i in range(item):
            array[pos] = num
            pos += 1
    return array

One thing we see that since we map values with the index we can’t sort an array having a negative value with this approach. So we slightly modify this method. We add the absolute value of the minimum element (negative) to all the elements. In this way, the 0th index will point to the element with the value 0. Once we have sorted the array we just subtract the same value from each element and we get the sorted array with negative and positive values. Modification to handle negative numbers as well:

def countSort(array):
    i_lower_bound , upper_bound = min(array), max(array)
    lower_bound = i_lower_bound
    if i_lower_bound < 0:
        lb = abs(i_lower_bound)
        array = [item + lb for item in array]
        lower_bound , upper_bound = min(array), max(array)
        
    counter_array = [0]*(upper_bound-lower_bound+1)
    for item in array:
        counter_array[item-lower_bound] += 1
    pos = 0
    for idx, item in enumerate(counter_array):
        num = idx + lower_bound
        for i in range(item):
            array[pos] = num
            pos += 1
    if i_lower_bound < 0:
        lb = abs(i_lower_bound)
        array = [item - lb for item in array]
    return array

Limitation of Counting sort

We can’t use counting sort in places where k is in the range (n²) because counting sort will take O(n^2) which is worse than comparison-based sorting algorithms. To solve this we use Radix Sort.

Radix Sort

The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses bucket sort as a subroutine to sort. This algorithm takes advantage of the fact that any number in the decimal system can be represented by digits from 0 to 9. So in this algorithm, we create buckets 10 buckets in every pass. For example, for a given array [121, 432, 564, 23, 1, 45, 788] there will be three passes. In each pass, the array is sorted by the corresponding pass place(LSB → MSB).

Radix Sort using counting sort as a subroutine:

def radixSort(array):
    n_digits = len(str(max(array)))
    size = len(array)
    for dgt in range(n_digits):
        count_array = [0]*10
        sorted_array = [0] * size
        for num in array:
            idx = (num//(10**dgt))%10
            count_array[idx] += 1
        
        for i in range(1, 10):
            count_array[i] += count_array[i - 1] 
        
        i = size - 1
        while i >= 0:
            idx = (array[i] // (10**dgt))%10
            sorted_array[count_array[idx] - 1] = array[i]
            count_array[idx] -= 1
            i -= 1
            
        array = sorted_array
return array

Using Counting sort to implement Radix sort makes the code slightly complex. To reduce the complexity we can use bucket sort as Subroutine. This makes the code more readable.

import itertools
def radixSort(array):
    n_digits = len(str(max(array)))
    for dgt in range(n_digits):
        buckets = [[] for i in range(10)]
        for num in array:
            idx = (num // (10**dgt)) % 10
            buckets[idx].append(num)
        array = list(itertools.chain(*buckets))
    return array

Modification to sort negative number as well:

def radixSort(array):
    min_num = min(array)
    if min_num < 0:
        lb = abs(min_num)
        array = [item + lb for item in array]
    n_digits = len(str(max(array)))
    for dgt in range(n_digits):
        buckets = [[] for i in range(10)]
        for num in array:
            idx = (num // (10**dgt)) % 10
            buckets[idx].append(num)
        array = list(itertools.chain(*buckets))
    if min_num < 0:
        lb = abs(min_num)
        array = [item - lb for item in array]
    return array

Hope this was helpful.