radix sort counting sort

Question

Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these number in linear time?

1)Counting Sort

2)Radix Sort

3)Bubble Sort

4)Merge Sort.

Comments

Could you please compare counting and Radix sort for this question.

---

no need for comparing here.

JUST GOOGLE WHEN WE USE COUNTING SORT  it happens because if range is very small and terms are repeating again and again like  (1,1,1,1,2,2,2,2 ,3,3) so no need for doing comparisons how much for counting sort. only then we use counting sort.

STILL SEE COUNTING SORT COMPLEXITY IS O(n + k)

where K = RANGE INPUT AND  N= TOTAL ELEMENTS TO SORT

SO  O ( n +n^6 ) = O(N^6)

---

WHEREAS RADIX sort go for big terms .

let me take radix sort time complexity takes O(d∗(n+b))time where b is the base, d is the numbers of digits present in the highest integer in the given range, and n is the numbers of integers to be sorted.

SO HERE TOTAL ELEMENTS   n^6 - 1

so   d = LOG (N^6 - 1 ) =6 log n = O(logn)

Value of base b is 10

SO TIME COMPLEXITY = O ( logn * ( n + 10 ) ) = O (NLOGN)

 

I THINK THIS WILL CLEAR EVERYTHING

---

Good Read:

https://stackoverflow.com/questions/1933759/when-is-each-sorting-algorithm-used