Counting Sort & Radix Sort

Counting Sort

Counting Sort is a non-comparison based sorting algorithm suitable for sorting integers within a limited range. It counts the occurrences of each element to determine their positions in the sorted output.

How Counting Sort Works

• Find the maximum element in the input array.
• Create a count array of size max+1 and initialize with zeros.
• Count the frequency of each element in the input array.
• Calculate the cumulative sum of counts to determine element positions.
• Place the elements at their correct positions in the output array.

Python Code Example

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    for num in arr:
        count[num] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    return output

# Usage Example
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

Radix Sort

Radix Sort is a non-comparison sorting algorithm that sorts numbers digit by digit starting from the least significant digit to the most significant, using a stable sorting algorithm like Counting Sort on each digit.

How Radix Sort Works

• Determine the maximum number to know the number of digits.
• Sort the array based on each digit (starting from least significant digit) using Counting Sort.
• Repeat for all digits until the array is fully sorted.

Python Code Example

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

# Usage Example
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)

Applications

• Counting Sort is efficient for small ranges of integers where comparisons are expensive.
• Radix Sort is suitable for sorting large numbers and strings (by representing them as integers).
• Used in scenarios needing linear-time sort complexities.