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 Sort Steps

counting sort steps

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]


Privacy Policy  |  Copyright@2017 - All Rights Reserved.  |  Contact us   |  Report website issues in Github   |  Facebook page   |  Google+ page

Email Facebook Google LinkedIn Twitter
^