COUNTING SORT
What is Counting Sort?
Counting sort is an arranging method which depends on the range of input values. It is utilized to sort components in direct time. In Counting sort, we store data in auxiliary array which definitely expands space necessity for the calculation execution.
It works very much like hashing, first, we ascertain the maximum value in the input array , the array to be arranged. At that point we tally the quantity of events of each array component from 0 to length-1 and appoint it into the auxiliary array. This array is utilized again to recover the arranged form of the input array .
In other words, counting sort runs on generally more modest arrangement of information. Counting sort ascertains, for each component in array , the quantity of components which are lesser than that particular component. It at that point utilizes this data to put that particular component straightforwardly into its situation in arranged array.
It really has straight time intricacy however we can’t say that it’s the best calculation on the grounds that the space intricacy is very high and it is simply appropriate to use in a situation where input array component territory is near the size of the exhibit.
Real World Example for Counting Sort
Assume, there are 10 boxes and 10 stones. Presently, you need to keep all these 10 stones in 10 boxes yet in an arranged request i.e., the littlest stone will be in the primary box and the biggest stone will be in the tenth. Obviously, there are a wide range of approaches to do this yet we should discuss one specific way which is identified with the counting sort. Now assume, you got a stone and you realize that there are by and large 5 stones which are more smaller than this stone, at that point without giving a solitary idea, you would put it in the sixth box. This is the specific thought behind the counting sort.
Accordingly in the counting sort, we need an additional array to store the yield like the boxes in the above example. This array will store every one of the numbers which are in the input, so the size of this array ought to be n.
Working of counting sort
- Discover the maximum component (let it be x) from the given array.
2. Initialize an array of length (x+1) with all components 0. This array is utilized for putting away the count of the components in the array.
3. Store the count of every component at their individual index in count array . For instance: In case the count of component 3 is 2, 2 is put away in the third position of count array. In the event that component “5” is absent in the array, 0 is put away in fifth position.
4. Store total sum of the components of the count array. It helps in putting the components into the right index of the arranged array.
5. Discover the list of every component of the first array in the count array. This gives the combined count. Spot the component at the record determined as demonstrated in figure underneath.
6. In the wake of setting every component at its right position, decrease its count by one.
Algorithm Pseudocode
Sortingbycount( Array , N)
x <- discover the maximum component in Array
Declare a count array of size (x+1)
Initialize the count array with all 0's
for p<- 0 to N
find the total repetition of each component and
store the tally at p th index in count Array
for p<- 1 to x
find the cumulative sum by adding current(p) and previous(p-1) count and store it in count Array itself.
for q<- N down to 1
Duplicate the component back into the input array
Decrement the count of each component duplicated by 1Counting Sort in Python
Counting Sort in Java
Counting Sort in C++
Time Complexity
1.Time taken to discover maximum is say k
2.Count array introduction will take k time
3.To keep up count array ,again k time
4.Presently direct emphasis of the input array to do the actual arranging
5.Since all the above advances are fixed for regardless of what the input array is, in this manner best, average and worst time complexity will continue as before i.e. remain same. Therefore,
Best Time Complexity : O(n+k), where n is the number of components in input array and k is the range of input
Average Time Complexity : O(n+k), where n is the number of components in input array and k is the range of input
Worst Time Complexity : O(n+k), where n is the number of components in input array and k is the range of input
where n is the number of components in input array and k is the range of input.
In the above cases, the complexity is on the grounds that regardless of how the components are put in the array, the calculation goes through (n+k) times.
Space Complexity
Auxiliary space is needed in Counting sort execution as we need to make a count array of size max+1
Henceforth space complexity is: O(max)/O(n+k) ,
where max is the maximum component of array & should be order of size of array.
So , greater the range of components, greater is the space complexity.
When to use counting sort?
Counting sort is utilized when:
there are more small numbers with various counts.
linear complexity is the need.
Key Points
1.Counting sort is proficient if the scope of input isn’t fundamentally more noteworthy than the quantity of objects to be arranged. Consider the circumstance where the input grouping is between range 1 to 10K and the input is 10, 5, 10K, 5K.
2. It’s anything but a correlation based arranging. It’s running time complexity is O(n) with space corresponding to the scope of input.
3. It utilizes two additional arrays.
4. Counting sort utilizes a halfway hashing to tally the event of the information object in O(1).
5. Moreover ,counting sort can be reached out to work for negative input sources .
6.There is no correlation between any components, so it is superior to comparison-based sorting. In any case, it is awful if the integers are very large because the array of that size ought to be made. It utilizes array indexing to decide the relative order of the input numbers.
7.It is stable. Numbers with a similar value show up in the result array as they show up in the input array.
8.It is regularly utilized as a sub-daily practice to another arranging calculation like radix sort.
Wrapping it up…
Sorting algorithms are a critical segment in the field of Computer Science. Being a non-comparison based sorting method, Counting Sort is exceptionally proficient given the scope of values is restricted.
