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)))
In the above python program, the steps followed are:
- Take a count of unique characters in the given array and store it in a variable at their respective index.
- Take the cumulative sum of the count and place the sum at respective indexes.
- 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.
- Repeat step 3 for all the unique element.
- When all the elements are placed, decrease the index in count variable and repeat the step 3.