Counting Sort Algorithm in Python

In this source code example, we will write a code to implement the Counting Sort algorithm in Python.

Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

Counting Sort Algorithm in Python

Counting Sort Algorithm:

countingSort(array, size)  max <- find largest element in array  initialize count array with all zeros  for j <- 0 to size    find the total count of each unique element and     store the count at jth index in count array  for i <- 1 to max    find the cumulative sum and store it in count array itself  for j <- size down to 1    restore the elements to array    decrease count of each element restored by 1

Python Program for Counting Sort Algorithm

# Counting sort in Python programmingdef countingSort(array):    size = len(array)    output = [0] * size    # Initialize count array    count = [0] * 10    # Store the count of each elements in count array    for i in range(0, size):        count[array[i]] += 1    # Store the cummulative count    for i in range(1, 10):        count[i] += count[i - 1]    # Find the index of each element of the original array in count array    # place the elements in output array    i = size - 1    while i >= 0:        output[count[array[i]] - 1] = array[i]        count[array[i]] -= 1        i -= 1    # Copy the sorted elements into original array    for i in range(0, size):        array[i] = output[i]data = [4, 2, 2, 8, 3, 3, 1]countingSort(data)print("Sorted Array in Ascending Order: ")print(data)

Output:

Sorted Array in Ascending Order: [1, 2, 2, 3, 3, 4, 8]

Related Algorithms in Python


Related Python Source Code Examples:

Python string literalsPython string length examplePython String join() method examplePython string split() method examplePython String index() method examplePython string find() method examplePython string startswith() method examplePython string endswith() method examplePython String lower() method examplePython String upper() method examplePython string title() method examplePython string capitalize() method examplePython string islower() method examplePython string istitle() method examplePython string isupper() method examplePython string swapcase() method examplePython string strip() method examplePython string replace() method examplePython string isdigit() method examplePython string isdecimal() method examplePython string isnumeric() method examplePython string isalpha() method examplePython string isalnum() method exampleWrite a python program to concatenate strings in different waysPython program to create a new string by appending s2 in the middle of s1Split a given string on asterisk into several substrings and display each substring in PythonWrite a Python program to count all lower case, upper case, digits, and special symbols from a given stringWrite a python program to return a string such that the string is arranged from lowercase letters and then uppercase lettersWrite a Python Class to Reverse a String Word by WordWrite a python class to implement pow(x, n)Write a python class to convert an integer to a Roman numeralWrite a python program to find the factorial of a number using recursionWrite a Python program to convert temperature in Celsius to FahrenheitWrite a Python program to find the largest number among the three input numbersWrite a Python program to print only even numbers using the functionWrite a python program to filter integer, float, string from a listWrite a python program to check whether the given number is greater than 50 and also divisible by 2 using nested if elseWrite a python program to demonstrate a simple class creationWrite a python program to demonstrate the object as an argumentWrite a python program to demonstrate an object as an argument with default valuesWrite a python program to demonstrate method overridingWrite a Python program for Linear Search and Binary SearchPython list - insert, remove, append, len, pop and clear exampleWrite a python program to add two numbersWrite a python program to get the python versionWrite a python program to check whether the first and last letters of the given word is vowel or not ?Write a python program to count the number of digitsWrite a python program to filter integer, float, string from a listWrite a python program to find the average of 10 numbersWrite a python program to traverse a list and print the values in itWrite a python program to print first 20 natural numbers using while loopWrite a python program to print the square of all numbers from 1 to 10Write a python program to get the sum of digitsWrite a python program to print right angle triangle pattern using *Write a python program to remove vowels in a wordWrite a python program to find absolute value using functionWrtie a python program to demonstrate the use of variable length argumentsWrite a python program to demonstrate the use of default argumentsWrite a python program to demonstrate the use of keyword argumentsWrite a python program to print a simple list using functionsWrite a python program to find the max values in a list using functionGiven a string of odd length greater 7, return a string made of the middle three chars of a given StringArrange string characters such that lowercase letters should come firstWrite a Python program to Count all lower case, upper case, digits, and special symbols from a given stringWrite a Python program to Find all occurrences in a given string ignoring the caseGiven an input string, count occurrences of all characters within a string and return the details as dictionaryWrite a Python program to Split a given string on asterisk into several substrings and display each substringWrite a Python program to Check whether the given string startswith 'h'Write a python program to concatenate strings in different waysWrite a python program to return a string such that the string is arranged from lowercase letters and then uppercase lettersWrite a python program to repeat a givent string multiple timesWrite a python program to create a simple list and nested list with different datatypesWrite a python program to add elements to an existing list from user inputWrite a python program to reverse a given listWrite a python program to convert a list to tuple using tuple functionWrite a python program to check whether the user given input is equal to the current working directory or notWrite a Python program for Linear Search and Binary SearchSelection Sort Algorithm in PythonBubble Sort Algorithm in PythonBogo Sort Algorithm in PythonBucket Sort Algorithm in PythonComb Sort Algorithm in PythonCounting Sort Algorithm in PythonHeap Sort Algorithm in PythonInsertion Sort Algorithm in PythonMerge Sort Algorithm in PythonQuick Sort Algorithm in PythonShell Sort Algorithm in PythonInterpolation Search Algorithm in PythonStack Implementation in PythonQueue Implementation in PythonDeque Implementation in PythonSingly Linked List Implementation in PythonDoubly Linked List Implementation in PythonCircular Linked List Implementation in PythonPriorityQueue Implementation in PythonCircular Queue Implementation in PythonBinary Search Tree Implementation in PythonStack Implementation Using Linked List in PythonStack Implementation Using Doubly Linked List in PythonPython - Convert Binary to Decimal ExamplePython - Convert Binary to Hexadecimal ExamplePython - Convert Binary to Octal ExamplePython - Convert Decimal to Binary ExamplePython - Convert Decimal to Octal ExamplePython Convert String to IntPython Convert String to DateTimePython Convert String to DatePython Convert String to JSONPython Convert String to NumberPython Convert String to ListPython Convert String to FloatPython Convert String to BytesPython Convert List to StringPython Convert List to SetPython Convert List to DictionaryPython Convert List to TuplePython Convert List to JSONPython Convert List to ArrayPython Convert List to String With CommasPython Convert List to DataframePython Convert Set to ListPython Convert Set to StringPython Convert Set to TuplePython Convert Set to DictionaryPython Convert Set to JSONPython Convert Set to Comma Separated StringPython Convert Dictionary to JSONPython Convert Dictionary to DataframePython Convert Dictionary to StringPython Convert Dictionary to ListPython Convert Dictionary Keys to ListPython Convert Dictionary Values to ListPython Convert Dictionary to TuplePython Convert Array to StringPython Convert Array to String With CommasPython Convert Array to ListPython Convert Array to SetPython Convert Array to JSONPython Convert Array to DictionaryPython Convert Array to TuplePython Convert Int to StringPython Convert Int to BinaryPython Convert Int to FloatPython Convert Date to StringPython Convert Date to EpochPython Convert Date to Unix TimestampPython Convert Date to DateTimePython Convert Date to DateTimePython Convert Date to TimestampPython Convert Date String to DateTimePython Convert Date String to EpochPython Convert Tuple to StringPython Convert Tuple to ListPython Convert Tuple to DictionaryPython Convert Tuple to Comma Separated StringPython Convert Tuple to ArrayPython Convert Tuple to JSONPython Convert JSON to StringPython Convert JSON to DictionaryPython Convert JSON to ArrayPython Convert JSON to XMLPython Convert JSON to List

Comments

Post a Comment