retagged by
806 views
1 votes
1 votes

Which sorting algorithm is good if we already knew the range of number -

Counting Sort OR Radix Sort

retagged by

1 Answer

3 votes
3 votes

It really depends on the given scenario and given resource constraints(memory and time). Time taken by counting sort is $O(n+k)$ when $n$ is size of input and $k$ is the range of input.Time taken by radix sort is $O(d(n+b))$ where $d$ is the maximum width of input number($1234$ has width of $4$), $n$ is the size of input and b is the $base$, usually base is $10$.

Consider this: you are given k decimal numbers in $range$ of $0$ to $n^{2}$ for some natural number $n$. Clearly time by counting sort is $O(n^{2})$.

But time by radix sort would take $O(dk)$, where $d$ is at most 19 in 64 bit compilers . That practically makes Radix sort linear time. So clearly here Radix sort beats Counting sort IN THIS CASE.

.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
2 answers
3
_Madhuri asked Oct 9, 2021
631 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
0 votes
0 votes
0 answers
4