The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
164 views

To sort the following numbers which algorithm will suit the best                                             

(i) 1 to 100 integers (ii) 0 to 1000000 integers                                  

 a)bucket sort for both

b) (i)radix sort   (ii)quick sort

c) (i)quick sort (ii)merge sort                                                                                             

 d) (i) merge sort (ii)quick sort

asked in Algorithms by Active (2.8k points) | 164 views
0

0 to 1000000 integers: since it is of a large set, quicksort will be efficient

0 to 100 integers: radix sort will be efficient

  

0
Where did you get BITS HD questions?
0
@Pankaj, Quick Sort will result in higher complexity O(n^2), isn't it?
0
Yes, but I read somewhere it is quite efficient for such size

2 Answers

+1 vote
Best answer
radix sorts time complexity is n (logn base b ) here base is 10 and if we convert 100 as 10^2 we get O(2*n) for radix sort hence efficient compared to others for integers from 0 to 100 and in second case quick sort is best as it doesnt speak anything about the input and it only speaks about the range the input can be in any order generally quicksort is considered "quick" in implementation as id doesnt use any auxilary arrays and is inplace  and it has no copying time like that of merge and the worst case can be avoided with randomised version of it hence 1. radix 2.quick sort
answered by Active (3.3k points)
selected by
0 votes

the option b is correct.

radix sort will take linear time.

quicksort will O(nlogn) time.

answered by (219 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,976 questions
45,471 answers
131,383 comments
48,425 users