Python Program to Implement Counting Sort


This is a Python program to implement counting sort.

Problem Description

The program sorts a list by counting sort.

Problem Solution

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.

Program/Source Code

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='')
Program Explanation

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.

Runtime Test Cases
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.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.