UGC NET CSE | Junet 2015 | Part 2 | Question: 48

Question

Which of the following algorithms sort $n$ integers, having the range $0$ to $(n^2 -1)$, in ascending order in $O(n)$ time?

• A. Selection sort
• B. Bubble sort
• C. Radix sort
• D. Insertion sort

Comments

Only Radix sort among options can sort in linear time i.e O(n)  rest are comparison sorts

so ans is C

Answer 1

ans c except radix sort all given algorithms take O(n^2) time so ans is radix sort it performs sorting digit by digits taking O(n) time

Answer 2

Radix sort take O(N) time .

Comments

how??? can u  explain..

---

Radix sort run loop = Max no. of digits in one Number and Number of digit is constant [can't be n].

so loop run n times only.

Answer 3

Selection sort takes O(n2) time.
Bubble sort takes O(n2) time.
Radix sort takes O(n) time.
Insertion sort takes O(n2) time.

So, option (C) is correct.

Answer 4

https://www.geeksforgeeks.org/radix-sort/