Python Tutorial

# Python Program for Counting Sort

## What is counting sort ?

Counting sort finds frequency of each array elements and array elements are sorted based on counter value of each elements.

## Counting Sort Algorithm

Finds maximum element in the list of elements.

Initialize counter list with 0 for all elements range from 0 to maximum element.

Finds frequency for all array elements and updates frequency value in counter list.

Sorted array elements based on counter list.

## Counting Sorting Time complexity

Counting sort time complexity is O(N+K), here N is the number of array elements. K is the maximum element in the array.

## Counting Sort Python Program

#!/usr/bin/python

def counting_sort(list_vals):

# finds max val in the list.
max_val = max(list_vals);

list_counts = [];
list_sorted = [];
# Initialize each elements count as 0
list_counts = [0 for i in range(0, max_val +1)];

# finds frequency of each array elements
for i in range(0, len(list_vals)):
list_counts[list_vals[i]] += 1;
# adds elements in sorted order based on frequency.
for i in range(0, max_val+1):
while (list_counts[i]>0):
list_sorted.append(i);
list_counts[i] -= 1;

return list_sorted;

if __name__ == "__main__":
list_vals = [3, 1, 2, 3, 6, 8, 5, 4];
print("Collection before sorting: %s" % str(list_vals));
print("Sorted list elements: %s" % str(counting_sort(list_vals)));
Output:
\$ python counting_sort.py
Collection before sorting: [3, 1, 2, 3, 6, 8, 5, 4]
Sorted list elements: [1, 2, 3, 3, 4, 5, 6, 8]

Python Tutorial