Counting Sort algorithm.

Counting Sort use case.


In computer science counting sort is a sorting method that uses the keys technique, it counts the number of objects having distinct key values. Then we have to find the position of each object in the output sequence.

New values in a temporary count array are used for sorting, so this sorting method is not a comparison-based and a not In Place algorithm. It is an integer sorting algorithm.

Counting sort algorithm.



It is assumed that values are going to be in a certain range (0 to 10 or 10 to 99 etc) and input data will be all real numbers. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. It is sometimes used as a sub-routine to another sorting techniques like radix sort.


Counting Sort Python code:




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

    # Initializing count array
    count = [0] * 10

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

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

    # Finding the index of each element in count array and placeputting the elements in result array
    i = size - 1
    while i >= 0:
        output[count[array[i]] - 1] = array[i]
        count[array[i]] -= 1
        i -= 1

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


data = [1, 3, 2, 5, 7]
counting_Sort(data)
print("Sorted elements in ascending order: ")
print(data)

OUT: Sorted elements in ascending order:
[1, 2, 3, 5, 7]





See also related topics: