Program for Counting Sort using Python

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

Program for Counting Sort using Python

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.

Author

  • Barry Allen

    A Full Stack Developer with 10+ years of experience in different domain including SAP, Blockchain, AI and Web Development.

    View all posts

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

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