Counting Sort

Counting Sort is an efficient sorting algorithm used with linear time complexity in the best, average, and worst cases. It is a non-comparative sorting algorithm that operates by counting the number of objects present in a collection and then creating a new collection with the objects based on the number of times they appear. Counting Sort is a stable sort, which means that equal elements retain their original position relative to each other in the sorted output.

This article will discuss the Counting Sort algorithm in detail and its time and space complexities. It will also include Python code examples for each topic, as well as five coding exercises with solutions to test the reader’s understanding of the material.

What is Counting Sort?

Counting Sort is a sorting algorithm used to sort a collection of elements. It is a non-comparative sorting algorithm that works by counting the number of objects present in a collection and then creating a new collection with the objects based on the number of times they appear. This is done by mapping the elements to the frequency of their occurrence in the collection.

Counting Sort works best on collections that have a small number of distinct elements. It is also a stable sort, which means that equal elements retain their original position relative to each other in the sorted output.

Counting Sort Algorithm

The Counting Sort algorithm works in two steps. The first step is to create an array, often referred to as a frequency array, that stores the number of times each element appears in the collection. The second step is to use the frequency array to create a sorted output.

Step 1: Create a frequency array

The first step of the Counting Sort algorithm is to create a frequency array. This array stores the number of times each element appears in the collection.

To create the frequency array, we first need to find the range of the elements in the collection. The range is the difference between the largest and smallest elements in the collection.

For example, if the collection contains elements from 0 to 9, the range is 9 (9 – 0 = 9).

Once we have the range, we can create an array with the same number of elements as the range. Each element in the array corresponds to an element in the collection. The value of each element in the array is the number of times the corresponding element appears in the collection.

For example, if the collection contains elements from 0 to 9, we would create an array of size 10 (0 to 9). The value of each element in this array is the number of times the corresponding element appears in the collection.

Let’s look at an example. Consider the following array:

collection = [2, 5, 3, 0, 2, 3, 0, 3]

The range of this array is 5 (5 – 0 = 5). So, we need to create an array of size 5. The value of each element in this array is the number of times the corresponding element appears in the collection.

For example, the value of the first element in the array is 2, because the element 0 appears twice in the collection. The value of the second element in the array is 2, because the element 1 does not appear in the collection. The value of the third element in the array is 3, because the element 2 appears three times in the collection, and so on.

The frequency array for the collection above is:

frequency_array = [2, 0, 3, 2, 0]

Step 2: Create a sorted output

The second step of the Counting Sort algorithm is to use the frequency array to create a sorted output. To do this, we first need to create a prefix sum array. A prefix sum array stores the cumulative sum of the elements in the frequency array.

For example, consider the frequency array from the example above:

frequency_array = [2, 0, 3, 2, 0]

The prefix sum array for this frequency array is:

prefix_sum_array = [2, 2, 5, 7, 7]

The prefix sum array stores the cumulative sum of the elements in the frequency array. The first element in the prefix sum array is the same as the first element in the frequency array, because there is no element before it. The second element in the prefix sum array is the sum of the first and second elements in the frequency array. The third element in the prefix sum array is the sum of the first, second, and third elements in the frequency array, and so on.

Once we have the prefix sum array, we can use it to create the sorted output. We start at the end of the prefix sum array and traverse backwards. For each element in the prefix sum array, we subtract 1 from its value. We then use this value as an index in the frequency array to find the corresponding element. This element is the element we want to add to the sorted output.

For example, for the prefix sum array above, we start at the end and traverse backwards. The last element in the prefix sum array is 7. We subtract 1 from this value and get 6. We then use this value (6) as an index in the frequency array and find the element at that index. The element at index 6 in the frequency array is 0. So, the element we want to add to the sorted output is 0.

We then repeat this process for the remaining elements in the prefix sum array. The next element in the prefix sum array is 7. We subtract 1 from this value and get 6. We then use this value (6) as an index in the frequency array and find the element at that index. The element at index 6 in the frequency array is 0. So, the element we want to add to the sorted output is 0.

We continue until we reach the first element in the prefix sum array. The sorted output for the example above is:

sorted_output = [0, 0, 2, 2, 3, 3, 3, 5]

Time Complexity

The time complexity of Counting Sort is linear in the best, average, and worst cases. The time complexity is O(n + k), where n is the number of elements in the collection and k is the range of the elements in the collection.

In the best case, when the elements in the collection are already sorted, Counting Sort will take O(n) time since we only need to traverse the collection once to create the frequency array.

In the average case, when the elements in the collection are randomly distributed, Counting Sort will take O(n + k) time since we need to traverse the collection once to create the frequency array and then traverse the frequency array once to create the sorted output.

In the worst case, when the elements in the collection are in reverse order, Counting Sort will take O(n + k) time since we need to traverse the entire collection and frequency array to create the sorted output.

Space Complexity

The space complexity of Counting Sort is O(k), where k is the range of the elements in the collection. This is because we need to create an array of size k to store the frequency of each element in the collection.

Python Code Examples

Let’s look at some Python code examples of the Counting Sort algorithm.

The first step of the Counting Sort algorithm is to create a frequency array. We can do this using the following Python code:

def count_sort(collection):
 
    # Get the range of the elements in the collection
    min_element = min(collection) # Get the minimum element in the collection
    max_element = max(collection) # Get the maximum element in the collection
    range = max_element - min_element + 1 # Calculate the range of the elements in the collection
 
    # Create an array of size range to store the frequencies of each element
    frequency_array = [0] * range
 
    # Iterate through the collection to count the frequency of each element
    for element in collection:
        frequency_array[element - min_element] += 1
 
    return frequency_array

The second step of the Counting Sort algorithm is to use the frequency array to create a sorted output. We can do this using the following Python code:

def count_sort(collection):
 
    # Get the range of the elements in the collection
    min_element = min(collection) # Get the minimum element in the collection
    max_element = max(collection) # Get the maximum element in the collection
    range = max_element - min_element + 1 # Calculate the range of the elements in the collection
 
    # Create an array of size range to store the frequencies of each element
    frequency_array = [0] * range
 
    # Iterate through the collection to count the frequency of each element
    for element in collection:
        frequency_array[element - min_element] += 1
 
    # Create a prefix sum array
    prefix_sum_array = [0] * range
    for i in range(1, len(prefix_sum_array)):
        prefix_sum_array[i] = prefix_sum_array[i - 1] + frequency_array[i - 1]
 
    # Create a sorted output array
    sorted_output = [0] * len(collection)
    for element in collection:
        sorted_output[prefix_sum_array[element - min_element]] = element
        prefix_sum_array[element - min_element] += 1
 
    return sorted_output

Conclusion

In this article, we discussed the Counting Sort algorithm in detail and its time and space complexities. We also saw some Python code examples of the algorithm. Counting Sort is a sorting algorithm used to sort a collection of elements. It is a non-comparative sorting algorithm that works by counting the number of objects present in a collection and then creating a new collection with the objects based on the number of times they appear. Counting Sort is an efficient sorting algorithm used with linear time complexity in the best, average, and worst cases. It is a stable sort, which means that equal elements retain their original position relative to each other in the sorted output.

Exercises

def count_sort(collection):
 
    # Get the range of the elements in the collection
    min_element = min(collection) # Get the minimum element in the collection
    max_element = max(collection) # Get the maximum element in the collection
    range = max_element - min_element + 1 # Calculate the range of the elements in the collection
 
    # Create an array of size range to store the frequencies of each element
    frequency_array = [0] * range
 
    # Iterate through the collection to count the frequency of each element
    for element in collection:
        frequency_array[element - min_element] += 1
 
    # Create a prefix sum array
    prefix_sum_array = [0] * range
    for i in range(1, len(prefix_sum_array)):
        prefix_sum_array[i] = prefix_sum_array[i - 1] + frequency_array[i - 1]
 
    # Create a sorted output array
    sorted_output = [0] * len(collection)
    for element in collection:
        sorted_output[prefix_sum_array[element - min_element]] = element
        prefix_sum_array[element - min_element] += 1
 
    return sorted_output
 
 
collection = [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2]
sorted_output = count_sort(collection)
print(sorted_output)

# Output: [0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 6]

def count_sort(collection):
 
    # Get the range of the elements in the collection
    min_element = min(collection) # Get the minimum element in the collection
    max_element = max(collection) # Get the maximum element in the collection
    range = max_element - min_element + 1 # Calculate the range of the elements in the collection
 
    # Create an array of size range to store the frequencies of each element
    frequency_array = [0] * range
 
    # Iterate through the collection to count the frequency of each element
    for element in collection:
        frequency_array[element - min_element] += 1
 
    # Create a prefix sum array
    prefix_sum_array = [0] * range
    for i in range(1, len(prefix_sum_array)):
        prefix_sum_array[i] = prefix_sum_array[i - 1] + frequency_array[i - 1]
 
    # Create a sorted output array
    sorted_output = [0] * len(collection)
    for element in collection:
        sorted_output[prefix_sum_array[element - min_element]] = element
        prefix_sum_array[element - min_element] += 1
 
    return sorted_output
 
 
collection = [-2, -5, -45, -66, -1000, 0, 1, 2, 5, 10]
sorted_output = count_sort(collection)
print(sorted_output)

# Output: [-1000, -66, -45, -5, -2, 0, 1, 2, 5, 10]

def count_sort(collection):
 
    # Get the range of the elements in the collection
    min_element = min(collection) # Get the minimum element in the collection
    max_element = max(collection) # Get the maximum element in the collection
    range = max_element - min_element + 1 # Calculate the range of the elements in the collection
 
    # Create an array of size range to store the frequencies of each element
    frequency_array = [0] * range
 
    # Iterate through the collection to count the frequency of each element
    for element in collection:
        frequency_array[element - min_element] += 1
 
    # Create a prefix sum array
    prefix_sum_array = [0] * range
    for i in range(1, len(prefix_sum_array)):
        prefix_sum_array[i] = prefix_sum_array[i - 1] + frequency_array[i - 1]
 
    # Create a sorted output array
    sorted_output = [0] * len(collection)
    for element in collection:
        sorted_output[prefix_sum_array[element - min_element]] = element
        prefix_sum_array[element - min_element] += 1
 
    return sorted_output
 
 
collection = [2, 1, 0, -1, -2, 0, 1, 0, -2]
sorted_output = count_sort(collection)
print(sorted_output)

# Output: [-2, -2, -1, 0, 0, 0, 1, 1, 2]