Teaching Kids Programming – Counting Sort Algorithm in Python

Teaching Kids Programming: Videos on Data Structures and Algorithms

The simple sorting algorithms (insertion sort, bubble sort, selection sort) and as well as Merge Sort and QuickSort are comparison based – they need to compare key elements. And they are general sorting algorithms that the best average running time is O(NLogN) (merge sort and quick sort).

We have O(N) time for best cases when array is already sorted if we go for improved bubble sorting and insertion sort algorithms. For worst cases when array is reverse sorted, the quick sort gives O(N^2) if pivot is selected badly.

Counting Sort Algorithm in Python

Counting sort algorithm is not based on comparisons. Rather, it counts each type of elements and then re-construct the sorted array. Let’s see the following counting sort implementation in Python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from collections import Counter
 
data = [-1, -5, 2, 3, 4, 5, 9, 10]
 
def countingSort(data):
    c = Counter(data)
    minv = min(c.keys())
    maxv = max(c.keys())
    ans = []
    for i in range(minv, maxv+1):
        ans.extend([i] * c[i])
    return ans
    
print(countingSort(data))
# [-5, -1, 2, 3, 4, 5, 9, 10]

from collections import Counter

data = [-1, -5, 2, 3, 4, 5, 9, 10]

def countingSort(data):
    c = Counter(data)
    minv = min(c.keys())
    maxv = max(c.keys())
    ans = []
    for i in range(minv, maxv+1):
        ans.extend([i] * c[i])
    return ans
    
print(countingSort(data))
# [-5, -1, 2, 3, 4, 5, 9, 10]

We use a Counter (hash table) to count the numbers, alternatively, we can count them in a static array. We need to find out the value ranges [min, max] and then by going through the numbers in the range, we append those existent elements in to the result sorted array.

The time complexity is O(N+R) where N is the number of the elements to sort, and R is the range size. The space complexity is O(N) as we are using a Counter object. If the range is big, then the Counting Sort is inefficient as it needs to iterate over the range. The counting sort is better used when the range is small e.g. sorting the students’ scores (which is from 0 to 100).

Counting sort is not stable – as we do not know how to distinguish between equal keys.

Sorting Algorithms (Teaching Kids Programming Tutorials)

• Teaching Kids Programming – Bubble Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – MergeSort Simply Explained
• Teaching Kids Programming – QuickSort Algorithm Simply Explained
• Teaching Kids Programming – Selection Sorting (Simple Sorting Algorithm)
• Teaching Kids Programming – Insertion Sort in Python (Simple Sorting Algorithm)
• Teaching Kids Programming – Counting Sort Algorithm in Python

–EOF (The Ultimate Computing & Technology Blog) —