Question

What is the median of three techniques in quick sort?

(a) quick sort with random partitions

(b) quick sort with random choice of pivot

(c) choosing median element as pivot

(d) choosing median of first, last and middle element as pivot

The question was asked at a job interview.

The query is from Sorting topic in chapter Sorting of Data Structures & Algorithms II

Answer 1

The correct answer is (d) choosing median of first, last and middle element as pivot

Easy explanation - In the median of three technique the median of first, last and middle element is chosen as the pivot. It is done so as to avoid the worst case of quick sort in which the time complexity shoots to O(n^2).