Python Program to Implement Counting Sort

Write a Python program that implements counting sort to sort a given list.

Counting Sort is a linear sorting algorithm that sorts a list of integers by counting the number of occurrences of each element and using that information to determine their correct positions in the sorted sequence.

Here is a step-by-step explanation of how Counting Sort works for given example [2, 1, 4, 1, 3, 6, 1, 8]:

• Step 1: Find the maximum element in the given list. In this case, the maximum element is 8.
• Step 2: Create a count list with a length equal to the maximum element + 1, initialized with all zeros.
• Step 3: Traverse the given list and increment the count at the corresponding index in the count list. Count occurrences of each element.
• [2, 1, 4, 1, 3, 6, 1, 8]
• Count List: [0, 0, 0, 0, 0, 0, 0, 0, 0]
• Count List after counting: [0, 3, 1, 1, 1, 0, 1, 0, 1]
• Step 4: Modify the count list by accumulating the counts. Each element in the count list represents the number of elements less than or equal to that index.
• Count List after modification: [0, 3, 4, 5, 6, 6, 7, 7, 8]
• Step 5: Create an output list with the same length as the given list.
• Step 6: Traverse the given list from right to left. For each element, find its position in the output list using the count list and decrement the count.
• [2, 1, 4, 1, 3, 6, 1, 8]
• Output List: [0, 0, 0, 0, 0, 0, 0, 0]
• Output List after sorting: [0, 0, 1, 1, 1, 2, 3, 4]
• The final output list is the sorted version of the given list: [1, 1, 1, 2, 3, 4, 6, 8].

Here is the source code of a Python program to implement counting sort. The program output is shown below.

def counting_sort(alist, largest):
    c = [0]*(largest + 1)
    for i in range(len(alist)):
        c[alist[i]] = c[alist[i]] + 1
 
    # Find the last index for each element
    c[0] = c[0] - 1 # to decrement each element for zero-based indexing
    for i in range(1, largest + 1):
        c[i] = c[i] + c[i - 1]
 
    result = [None]*len(alist)
 
    # Though it is not required here,
    # it becomes necessary to reverse the list
    # when this function needs to be a stable sort
    for x in reversed(alist):
        result[c[x]] = x
        c[x] = c[x] - 1
 
    return result
 
 
alist = input('Enter the list of (nonnegative) numbers: ').split()
alist = [int(x) for x in alist]
k = max(alist)
sorted_list = counting_sort(alist, k)
print('Sorted list: ', end='')
print(sorted_list)

1. Create a function counting_sort that takes a list and a variable largest as arguments.
2. Inside the function create a list c of zeros of length largest + 1.
3. For each element n in the input list, increment the nth index of the list c.
4. The list c now contains the frequency of each element in the input list.
5. For each index from 1 to the length of c – 1, add to the current element the previous element. Before the loop, decrement c[0] since this will cause all the elements to be decremented by one after the loop finishes. Thus, the list c will contain the last index of each element in our sorted array.
6. Create the output array with size the same as that of the input array.
7. Create a loop that iterates over the elements of the input list in reverse.
8. In each iteration of the loop set the pth element of the output list equal to the element of the input list being iterated over. The value x is the element of the list c with index equal to the element of the input list. The value where x is stored in c is then decremented.
9. The sorted list is displayed.

Time Complexity: O(n+k)
The time complexity of the counting sort algorithm is O(n+k), where n is the number of elements in the input list and k is the range of values in the list.

Space Complexity: O(n+k)
The space complexity of the program is O(n+k), as it requires additional space for the count array and the result array, both of which have sizes proportional to n and k.

Testcase 1: Here is the given list [2, 1, 4, 1, 3, 6, 1, 8] for sorting using the counting sort algorithm.

Enter the list of (nonnegative) numbers: 2 1 4 1 3 6 1 8
Sorted list: [1, 1, 1, 2, 3, 4, 6, 8]

Testcase 2: Here is the given list [7, 5, 4, 3, 2] for sorting using the counting sort algorithm.

Enter the list of (nonnegative) numbers: 7 5 4 3 2
Sorted list: [2, 3, 4, 5, 7]

• Counting sort has a linear time complexity, making it efficient for large input sizes.
• It is a stable sorting algorithm, preserving the relative order of elements with equal values.
• Counting sort works well when the range of input values is small and known in advance.

• Counting sort requires extra memory to store the count array, which can be a limitation for large input ranges.
• It is not suitable for sorting floating-point numbers or negative numbers without modification.
• Counting sort’s performance can degrade if the range of input values is significantly larger than the number of elements.

To practice programs on every topic in Python, please visit “Programming Examples in Python”.