Counting Sort Sorting Algorithm (Working with Diagram) | Part - 1 | Sorting Algorithms - DSA

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. This mapping is done by performing arithmetic calculations on those counts to determine the positions of each key value(unique element) in the output sequence.
Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items.
It is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.
Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log n) lower bound for comparison sorting does not apply to it.
Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)
---------------------------------------------------------------------------------------------
Full DSA playlist -    • Introduction to Data Structures & Alg...  
Full Code & Theory article - https://simplesnippets.tech/counting-...
C++ Programming Tutorials for Beginners Course -    • Introduction to Computer Programming ...  
---------------------------------------------------------------------------------------------
Support Simple Snippets by Donations -
Google Pay UPI ID - tanmaysakpal11@okicici
PayPal - paypal.me/tanmaysakpal11
---------------------------------------------------------------------------------------------
Simple Snippets Official Website -
http://simplesnippets.tech/
Simple Snippets on Facebook -
  / simplesnippets  
Simple Snippets on Instagram -
  / simplesnippets  
Simple Snippets on Twitter -
  / simplesnippet  
Simple Snippets Google Plus Page -
https://plus.google.com/+SimpleSnippets
Simple Snippets email ID -
[email protected]

For More Technology News, Latest Updates and Blog articles visit our Official Website - http://simplesnippets.tech/
#countingsort #sortingalgorithm #datastructures #dsa #dsalgo