Quiz on sorting

#1

Which of the following changes to typical QuickSort improves its performance on average and are generally done in practice?

  1. Randomly picking up to make worst case less likely to occur.
  2. Calling insertion sort for small sized arrays to reduce recursive calls.
  3. QuickSort is tail recursive, so tail call optimizations can be done.
  4. A linear time median searching algorithm is used to pick the median, so that the worst case time reduces to O(n Log n)

which option is correct and why

#2

First refer these links:


https://gateoverflow.in/13321/following-quicksort-improves-performance-generally-practice

It is a completely theoretical question. You have to read all the materials there to understand it completely. Just google the terms which you cannot understand.

You know from the lecture that we use Randomized quick sort as its worst case complexity is O(nlogn) whereas the normal quick sort has a worst case complexity of O(n^2).So 1st option will surely be an answer.
Option 3 is also correct. You can read it from here https://www.geeksforgeeks.org/tail-recursion/
Option 2 is correct and is used in Hybrid Quicksort algorithm. You can read about its theory from here https://www.techiedelight.com/hybrid-quicksort/

Last option is incorrect as finding a median is O(n) operation. In quick sort, for each subarray, you will have to find the median so the worst case of the sorting will be O(n^2)

Read the articles in the link to understand clearly.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.