Introduction

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

Program

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)))

Output

Explanation

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.