Sunday, May 18, 2008

Fresher Interview questions on Sorting - Quick Sort


Here are some of the commonly asked and good questions on quick sort.

Determine the running time of QuickSort for

a.Sorted input
b.reverse -ordered input
c.random input
d. When all the elements are equal

The ones who are familiar with QuickSort as also well aware of the important phase of the algorithm-the pivot selection.Suppose we always choose the middle element as the pivot .Does this make it unlikely that QuickSort will require quadratic time?

What is the worst-case behavior (number of comparisons) for quick sort?
link to solution
In selecting the pivot for QuickSort, which is the best choice for optimal partitioning:
a.The first element of the array
b.The last element of the array
c.The middle element of the array
d.The largest element of the array
e.The median of the array
f.Any of the above
link to solution

In its worst case QuickSort behaves like:
a.Bubble sort
b.Selection sort
c.Insertion sort
d.Bin sort
link to solution

Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted.

Recall that the linked-list version of quicksort() puts all items whose keys are equal to the pivot's key into a third queue, which doesn't need to be sorted. This can save much time if there are many repeated keys.

The array-based version of quicksort() does not treat items with equal keys specially, so those items are sorted in the recursive calls.

Is it possible to modify array-based quicksort() so that the array is partitioned into three parts (keys less than pivot, keys equal to pivot, keys greater than pivot) while still being in-place? (The only memory you may use is the array plus a constant amount of additional memory.)