Interview questions on Sorting - Quick Sort

QuickSort

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

1. Determine the running time of QuickSort for
   
   a.Sorted input
   b.reverse -ordered input
   c.random input
   d. When all the elements are equal
   
   link to solution
   
   



2. 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?
   
   link to solution
   
   



3. What is the worst-case behavior (number of comparisons) for quick sort?
   link to solution
   



4. 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
   



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




6. 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.
   link to solution
   



7. 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.)
   
   Why or why not?
   
   link to solution