MODIFIED QUICKSORT Consider the modification of the deterministic quicksort algo
ID: 3930694 • Letter: M
Question
MODIFIED QUICKSORT
Consider the modification of the deterministic quicksort algorithm described in class so that, instead of selecting the first element in an nn-element sequence as the pivot, we choose the element at index n/2n/2, that is, an element in the middle of the sequence.
(a) What is the running time of this version of quicksort on a sequence that is already sorted? Use O-notation; you do not need to explain your answer.
(b) Describe an input sequence that would cause this version of quick-sort to run in (n2)(n2) time.
Explanation / Answer
a)
Picking the middle element of a sorted array as the pivot results in a balanced split. So the running time satisfies
the recursion T(n) = 2T(n/2) + n 1. This is the same recursion as for merge-sort, which has running time n
log n n + 1 or (n log n).
b)
For an input of size 8, use 8, 6, 4, 2, 1, 3, 5, 7 or 1, 3, 5, 7, 8, 6, 4, 2 or 4, 3, 2, 1, 8, 7, 6, 5 or 6, 4, 7, 1, 8, 2, 3, 5,
etc. The pattern should be that, at any point, the middle element, which is the one being removed, is the smallest
largest number of the current array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.