Python Program to Implement Counting Sort

This is a Python program to implement counting sort.

The program sorts a list by counting sort.

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 p is the element of the list c with index equal to the element of the input list. The value where p is stored in c is then decremented.

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. The user is prompted to enter a list of numbers.
2. The largest number in the list is found.
3. The list and the largest number are passed to the counting_sort function and the sorted list is returned.
4. The sorted list is displayed.

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

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.