Python Tutorial
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 time complexity is O(N+K), here N is the number of array elements. K is the maximum element in the array.
#!/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
Privacy Policy | Copyright2020 - All Rights Reserved. | Contact us
| Report website issues in Github
| Facebook page
| Google+ page