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.
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
3. Insertion Sort Time Complexity
4. Runtime Reduction of a Linear Search
5. Selection Sort Time Complexity
6. Bubble 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