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

__link to solution__ - 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__ - 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.
__link to solution__ - 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__

Suppose we have an array of N elements containing three distinctive keys, true, false and maybe. Give an O(N) algorithm to rearrange the list so that all false elements precede maybe elements, which in turn precede true elements. You may only use constant extra space.

ReplyDeleteGreat and Useful Article.

ReplyDeleteJava Online Training

Online Java Course

Java Course Online

J2EE training

online J2EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai