Program for Counting Sort using Python


The task is to sort the given array element using Counting sort. Counting sort is based on key between specific range.


def sort(arr):
    char = [0 for i in range(256)]
    char_count = [0 for i in range(256)]
    result = ["" for _ in arr]
    for i in arr:
        char_count[ord(i)] += 1
    for i in range(256):
        char_count[i] += char_count[i - 1]
    for i in range(len(arr)):
        char[char_count[ord(arr[i])] - 1] = arr[i]
        char_count[ord(arr[i])] -= 1
    for i in range(len(arr)):
        result[i] = char[i]
    return result

ip_arr = "gocoding"
output = sort(ip_arr)
print("The sorted array is %s " %("".join(output)))


Program for Counting Sort using Python


In the above python program, the steps followed are:

  1. Take a count of unique characters in the given array and store it in a variable at their respective index.
  2. Take the cumulative sum of the count and place the sum at respective indexes.
  3. Pick the element from the input array, and check the cumulative sum of the element in count array. Decrease the sum by 1 and place the element at that index.
  4. Repeat step 3 for all the unique element.
  5. When all the elements are placed, decrease the index in count variable and repeat the step 3.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.