Easy Tutorial
❮ Python Os Tcsetpgrp Python File Readlines ❯

Python Counting Sort

Python3 Examples

The core of counting sort is to convert the input data values into keys stored in an extra array space. As a sorting algorithm with linear time complexity, counting sort requires the input data to be integers within a definite range.

Example

def countSort(arr): 

    output = [0 for i in range(256)] 

    count = [0 for i in range(256)] 

    ans = ["" for _ in arr] 

    for i in arr: 
        count[ord(i)] += 1

    for i in range(256): 
        count[i] += count[i-1] 

    for i in range(len(arr)): 
        output[count[ord(arr[i])]-1] = arr[i] 
        count[ord(arr[i])] -= 1

    for i in range(len(arr)): 
        ans[i] = output[i] 
    return ans  

arr = "wwwtutorialprocom"
ans = countSort(arr) 
print ( "Sorted character array: %s"  %("".join(ans)) )

Executing the above code produces the following result:

Sorted character array: bcmnoooruwww

Python3 Examples

❮ Python Os Tcsetpgrp Python File Readlines ❯