QuickSort
Here are some of the commonly asked and good questions on 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?
- 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
- In its worst case QuickSort behaves like:
a.Bubble sort
b.Selection sort
c.Insertion sort
d.Bin sort
- 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.)
Why or why not?
No comments:
Post a Comment