CS 521: Data Structures and Algorithms I
Fall 2019 (Homework 2)
1. A Better Quick Sort (or is it?)
Professor Ash has invented a way to make Quicksort run quickly in the worst case. To sort an
array of n elements, his
...
CS 521: Data Structures and Algorithms I
Fall 2019 (Homework 2)
1. A Better Quick Sort (or is it?)
Professor Ash has invented a way to make Quicksort run quickly in the worst case. To sort an
array of n elements, his Ash-sort algorithm first takes a sample of 2pn + 1 elements out of the
array and sorts them with insertion sort. Next, he takes the median of the sorted sample, which
he can determine by simply looking at the middle element of the sample, and uses it to partition
the array of n elements. Finally, he recursively sorts the two sub-arrays of the partition just as in
Quicksort.
1.a. (5 Pts.) Argue that the recurrence for the worst-case running time T (n) of Ash-sort is
T (n) = T (n − pn) + T (pn) + θ(n)
solution:
1. Insertionsort sample: O((2pn + 1)2) = O(n)
2. Median: O(1).
3. Partition: Θ(n)
4. Recursively solve 2 subproblems:
since there are at least pn elements are smaller than the pivot, and there are at least pn
elements which are larger than the pivot, the smaller side of the partition has at least pn
elements and the larger side has at most (n − pn) elements. Quicksort performs worst when
the imbalance is maximal, so the time is T (n − pn) + T (pn).
Summing 1-4 yields the recurrence.
1.b. (5 Pts.) Sketch a work tree for the equation in part (a). Label the work in at least the top 3
levels of the tree, as well as the work at the leaves.
1.c. (10 Pts.) Argue that the height h(n) of the work tree satisfies the recurrence
h(n) = h(n − pn) + 1:
Show that h(n) = O(pn).
solution: Use the substitution method to show that h(n) = O(pn). The height of the
recursion tree for n-element Mosesort is 1 plus the height of the root’s tallest subtree. The
tallest subtree is the one with n − sqrtn, hence h(n) = h(n − sqrtn) + 1.
Guess h(n) ≤ cpn for some c > 0. Substitution:
[Show More]