Python program for Counting sort Algorithm
Counting sort is a sorting technique based non keys between the specific range.It works by counting the number of objects having distinct key values(knd of hashing).Then it
calculates the position for each object in the output sequence.
The Time complexity is O(n^2)
class Sort(): #Default constructor for the class Sort def __init__(self, ele_list): self.ele_list = ele_list #Function for count sort def count_sort(self): output = [0 for i in range(256)] count = [0 for i in range(256)] #storing the result as string is immutable ans = ["" for _ in self.ele_list] #Store count of each character for i in self.ele_list: count[ord(i)] += 1 #It stores the actual position of alphabets for i in range(256): count[i] += count[i - 1] #Build the output character array for i in range(len(self.ele_list)): output[count[ord(self.ele_list[i])] - 1] = self.ele_list[i] count[ord(self.ele_list[i])] -= 1 #The sorted array for i in range(len(self.ele_list)): ans[i] = output[i] return ans #Main function def main(): ele_list = "cppsecrets" #Object for the class Sort obj_Sort = Sort(ele_list) ans = obj_Sort.count_sort() print("Sorted character array is: ",ans) #Driver code if __name__ == "__main__": main() OUTPUT: Sorted character array is: ['c', 'c', 'e', 'e', 'p', 'p', 'r', 's', 's', 't']
Comments