Want to sort numbers in a given range? Use Counting sort algorithm.
Counting sort is a integer sorting algorithm, It is a non-comparison sorting algorithm as it does not compare different elements rather it uses index of elements and their count while sorting them. Counting sort is a linear sorting algorithm and must be used when elements are in a given range and variation in the elements is not much.
It simply operates by counting the number of occurrences of different elements in a given range, as it is a linear sorting technique it has time complexity of O(n + k) where 'n' is the number of elements in the array and 'k' is the number of elements between max and min elements.
let us consider the below example,
let the array of numbers to be sorted be
arr = {1,3,2,1,3,3,2}
here, n = 7, min = 1, max = 3 hence k = 3
now we create a array that holds counts of all the elements, 1 has occurred 2 times, 2 has occurred 2 times and 3 has occurred 3 times thus we have
count_Array = {2, 2, 3}
Now, we construct sorted array using the count_Array, as we know 1 has occurred 2 times in the sorted array we put it 2 times and so on finally we have sorted array as
Algorithm
- Find the minimum and maximum element from the given array.
- Initialize a count array with length as maximum - maximum and initialize all elements to 0.
- Traverse thorough the original array and keep updating the count of each element.
- Use the count array to place the sorted elements in the original array, using the count of each element.
Though the algorithm has very less time complexity it cannot be used in general sorting cases, it can be only used when elements to be sorted are to be known in particular range.
C++ Program
Sample input and output to check the program
Quick Sort using Recursion
Data Encryption using Caesar Cipher
Data Decryption using Caesar Cipher
LCM of 2 numbers
Anagram Strings
Double Linked List
Finding Middle node in a Linked List
Comments
Post a Comment