Question

What is a randomized quick sort?

(a) quick sort with random partitions

(b) quick sort with random choice of pivot

(c) quick sort with random output

(d) quick sort with random input

I got this question in an interview.

This is a very interesting question from Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

Correct choice is (b) quick sort with random choice of pivot

The best I can explain: Randomized quick sort chooses a random element as a pivot. It is done so as to avoid the worst case of quick sort in which the input array is already sorted.