Counting Sort Algorithm
FREE
Counting Sort Algorithm is a sorting algorithm that works best when you have a small range of numbers to sort. Instead of comparing elements like in other sorting methods, it counts how many times each number appears and then puts them in order based on that count. This makes it really fast when the range of numbers is not too big compared to the total number of items to be sorted.
Working of counting Sort Algorithm
- Determine the maximum element, denoted as "max," from the provided array.
- Create an array of length "max+1" with all elements initialized to 0. This array serves the purpose of storing the count of each element present in the given array.
- Assign the count of each element to their corresponding index in the count array.
- Calculate the cumulative sum of the elements in the count array. This cumulative sum assists in correctly positioning the elements in the sorted array.
- Determine the index of each element from the original array in the count array, yielding the cumulative count. Place each element at the calculated index position in the sorted array, as illustrated in the figure below.
- Once each element is correctly positioned, decrement its count by one in the count array.
Implementation of counting sort Algorithm
Counting sort in Java
Output:
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Counting sort in C/C++
Output:
Counting sort in Python
Output:
Complexity Analysis of Counting Sort Algorithm
Turn Learning into Career Growth
Time Complexity of Counting Sort Algorithm
The time complexity of the algorithm is O(N+M), where N denotes the size of the input array and M is the size of the count array. This holds true for worst-case, average-case, and best-case scenarios.
Space Complexity of Counting Sort Algorithm
The Space Complexity is O(N+M), accounting for the space used by the output array and the count array.
Applications of Counting Sort Algorithm
- Counting sort Algorithm is employed for sorting arrays containing smaller integers with numerous repetitions.
- It's chosen when achieving linear time complexity is crucial for efficient sorting operations.
- Its effectiveness lies in efficiently handling scenarios where elements have limited range and frequent repetitions.
Advantage of Counting Sort Algorithm
- Counting sort outperforms comparison-based sorting algorithms, like merge sort and quicksort, for inputs with a range comparable to the input size.
- It offers simplicity in implementation, making it straightforward to code.
- Counting sort maintains stability, preserving the original order of elements with equal values in the sorted output.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Disadvantage of Counting Sort Algorithm
- Counting sort is incompatible with decimal values, limiting its applicability in sorting operations involving non-integer data.
- Its efficiency diminishes significantly when sorting a large range of values, rendering it inefficient for such scenarios.
- As a non-in-place sorting algorithm, counting sort necessitates additional space to store auxiliary data, impacting its memory usage compared to in-place algorithms.
Conclusion
- Counting Sort Algorithm provides an efficient means of sorting arrays with small integer values and numerous repetitions.
- Its linear time complexity makes it ideal for scenarios where achieving fast sorting operations is crucial.
- Counting Sort maintains stability, preserving the original order of elements with equal values.
- Despite its effectiveness, Counting Sort is limited by its inability to handle decimal values and its decreased efficiency with large range inputs.
- Nevertheless, its simplicity in implementation and ability to handle repetitive elements efficiently contribute to its practical significance.
- Careful consideration of the input data characteristics is essential to determine Counting Sort's suitability for specific sorting tasks.
Thanks for reading. May the code be with you 🙂
Code with Precision! Enroll in Scaler Academy's Online DSA Certification Course and Master Efficient Algorithms.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more