Counting Sort Time Complexity | Counting Sort Python

You are thinking that is there any sorting algorithm that performs better than the Quicksort or Mergesort or selection sort? Another question also arises in the mind, is there any sorting algorithm that beat the O (n log n) time complexity? The answer is counting sort. But it is limited by some rules. The counting sort only works on positive numbers with a max number in the array. By this process, this algorithm's time complexity is lower than the others. The counting sort time complexity with the implementation of this algorithm will be discussed in this post. 

Introduction of the counting sort

The counting sort is a sorting algorithm that performs on the non-negative numbers with a max number in the array. This algorithm sort an array based on the occurrence of each unique number in the array. 


The time complexity of the counting sort

The measurement of a simple algorithm depends on the input length size and the number of 'for' loops used in the implementation. To find out the time complexity of the counting sort algorithm, we have to understand the algorithm or pseudocode of this algorithm. This way we learn this better.


Pseudocode for the Counting Sort

Output_array ← input size length array 0's ← array[0] * input length

Count_array ← input size length with max of the array length size 0's ← array[0] * input length * max number


function CountingSort(Input_array, Length, Count_array, Output_array)

    for i = 0 to Length  do

        Count_array[Input_array[i]] += 1


    for i = 1 to Length * max(Count_array)  do

        Count_array[i] += Count_array[i-1]


    for i = Length-1 to -1  do

        Output_array[Count_array[Input_array[i]] - 1] = Input_Array[i]

        Count_array[Input_Array[i]] -= 1


     for i = 1 to Length  do

        Count_array[i] += Ouput_array[i-1]


The four loops time complexity

The first loop is used for the storage of each number of the input array. The cumulative sum for the count array is done for each element or number in the second array. Then, the indexing of every number is processed in the third array. Finally, the output result is made in the fourth.


counting sort time complexity

Fig. 01: Counting Sort Time Complexity

The first, second, and fourth arrays run in a range for the input length size. So, the time complexity of those arrays will be,

Time Complexity = O ( input array length )

                = O (n) 

Here, 'n' is the input array length.


The third only run to the maximum numbers of the array for the indexing of the array for each element. Here another time complexity occurs. This running process length is the same as the Big O (n). Then, the time complexity for this loop,

Time Complexity = O ( indexing each element for the max number )

                = O (N)

Here, 'N' max number of the array for indexing.

At last, the time complexity of the counting sort is,

Time Complexity = O ( max number of the array for indexing + the input array length )

                = O ( N + n)


Read Similar Post

1. Merge Sort Time Complexity

2. Quick Sort Time Complexity

3. Insertion Sort Time Complexity

4. Runtime Reduction of a Linear Search

5. Selection Sort Time Complexity

6. Bubble Sort Time Complexity

7. Heap Sort Time Complexity 

8. Binary Search Tree Time Complexity


Counting Sort in Python

Now, the counting sort will be implemented below according to the pseudocode mentioned in the post. This python code for counting sort is special from the other code on the web. The below code works for any length of the input array for the counting sort.


def TheCountingSort(C_Array, length, Count_Array, Output_Array):
    for
i in range(0, length):
       
Count_Array[C_Array[i]] += 1

   
for i in range(1, length* max(C_Array)):
       
Count_Array[i] += Count_Array[i - 1]

   
for i in range(length-1, -1, -1):
       
Output_Array[Count_Array[C_Array[i]] - 1] = C_Array[i]
       
Count_Array[C_Array[i]] -= 1

   
for i in range(0, length):
       
C_Array[i] = Output_Array[i]

if __name__=='__main__':
   
n = int(input())
   
C_Array = list(map(int, input().split()))
   
Output_Array = [0] * len(C_Array)
   
Count_Array = [0] * len(C_Array)* max(C_Array)
   
TheCountingSort(C_Array, len(C_Array), Count_Array, Output_Array)
   
print(C_Array)

Sample Input:

20
9 8 7 6 5 4 3 2 1 0 15 14 12 13 11 90 91 92 94 93

Sample Output: 

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 90, 91, 92, 93, 94

Post a Comment

Previous Post Next Post