Counting Sort for Limited Range

Counting Sort for Limited Range

The Counting Sort Algorithm is a non-comparison-based sorting algorithm that is highly efficient when the range of input values is limited (i.e., the difference between the maximum and minimum values is small compared to the number of elements). It works by counting the occurrences of each value in the input array, then using these counts to place elements in their correct positions in the output array. Counting sort is stable and has a time complexity of O(n + k), where n is the number of elements and k is the range of input values.

Example:

• Input: nums = [4, 2, 2, 8, 3, 3, 1]
• Output: [1, 2, 2, 3, 3, 4, 8]
• Explanation: The array is sorted in ascending order, assuming the range of values is small (e.g., 0 to 8).

def countingSort(nums):
    # Find the range of the input
    max_val = max(nums)
    min_val = min(nums)
    range_val = max_val - min_val + 1
    
    # Initialize count array
    count = [0] * range_val
    output = [0] * len(nums)
    
    # Count occurrences of each value
    for num in nums:
        count[num - min_val] += 1
    
    # Compute cumulative count
    for i in range(1, range_val):
        count[i] += count[i - 1]
    
    # Build the output array
    for num in reversed(nums):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output

# Example usage
nums = [4, 2, 2, 8, 3, 3, 1]
print(countingSort(nums))  # Output: [1, 2, 2, 3, 3, 4, 8]

[1, 2, 2, 3, 3, 4, 8]

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE