← Back to Data Structures and Algorithms in Python

In this source code example, we will write a code to implement the Counting Sort algorithm in Python.

Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

Counting Sort Algorithm in Python

Counting Sort Algorithm:

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Python Program for Counting Sort Algorithm

# Counting sort in Python programming

def countingSort(array):
    size = len(array)
    output = [0] * size

    # Initialize count array
    count = [0] * 10

    # Store the count of each elements in count array
    for i in range(0, size):
        count[array[i]] += 1

    # Store the cummulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Find the index of each element of the original array in count array
    # place the elements in output array
    i = size - 1
    while i >= 0:
        output[count[array[i]] - 1] = array[i]
        count[array[i]] -= 1
        i -= 1

    # Copy the sorted elements into original array
    for i in range(0, size):
        array[i] = output[i]


data = [4, 2, 2, 8, 3, 3, 1]
countingSort(data)
print("Sorted Array in Ascending Order: ")
print(data)

Output:

Sorted Array in Ascending Order: 
[1, 2, 2, 3, 3, 4, 8]

Related Algorithms in Python

1. Write a Python program for Linear Search and Binary Search
2. Selection Sort Algorithm in Python
3. Bubble Sort Algorithm in Python
4. Bogo Sort Algorithm in Python
5. Bucket Sort Algorithm in Python
6. Comb Sort Algorithm in Python
7. Counting Sort Algorithm in Python
8. Heap Sort Algorithm in Python
9. Insertion Sort Algorithm in Python
10. Merge Sort Algorithm in Python
11. Quick Sort Algorithm in Python
12. Shell Sort Algorithm in Python
13. Interpolation Search Algorithm in Python

← Back to Data Structures and Algorithms in Python