edited by
571 views
1 votes
1 votes

Why might quick sort be preferred over insertion sort and merge sort?

  1. The worst-case asymptotic algorithmic complexity of quick sort is superior to that of insertion sort and merge sort.
  2. In situations where little temporary space is available, merge sort cannot be used, and in such cases, the average-case asymptotic algorithmic complexity of quick sort is superior to that of insertion sort.
  3. Quick sort is a stable sort, whereas insertion sort and merge sort are not.
  4. When random access is very slow, as with sorting records on a long tape, the average run time of quick sort is superior to that of insertion and merge sort.
edited by

2 Answers

Best answer
2 votes
2 votes

Choice A is false because the asymptotic algorithmic complexity of quick sort is O(n2), whereas that of insertion sort is O(n2) and that of merge sort is O(n log2 n).


Choice B is true. The average asymptotic algorithmic complexity of quick sort is O(n log2 n), whereas that of insertion sort is O(n2) and that of merge sort is O(n log2 n). But when merge sort cannot be used, quick sort is certainly a reasonable alternative.


Choice C is false because quick sort is not a stable sort, but insertion sort and merge sort are stable. That is, quick sort may invert equal elements during partitioning, whereas insertion and merge sort never invert equal elements at any step.

Choice D is false because quick sort really needs to do many random accesses. In contrast, merge sort needs very few random accesses.

selected by
1 votes
1 votes

Weel it seems like, there is a confusion that why D should not be correct answer??

Now, as the Staement suggests 

When random access is very slow

And besides comparing all other option,in B when there is little space abvailable ,merge sort will be totaly inefficient plus the feature of Randomised Quick sort.comes into play...Both follows Always

So B should be the answer

Thnk it other Way!!!

If Random access is Fast ,but still extra memory is very less then we can't perform merge sort..so option D is surpressed by Option B here again

edited by
Answer:

Related questions

1 votes
1 votes
1 answer
1
Bikram asked Jan 24, 2017
258 views
Which of the following sorting algorithms has the lowest best-case asymptotic algorithmic complexity?Selection sortMerge sortInsertion sortHeap sort