# Counting Sort Algorithm 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]``````