next up previous
Next: About this document

Fundamental Algorithms, Spring 1998

Assignment 3. Heapsort and quicksort.

Given February 4, due Monday, February 16.

The quick select selects the largest x fraction of the elements of an array in O(n) time for an array of size n. Here x is a number between 0 and 1. Now, suppose there are k such numbers tex2html_wrap_inline29 and we want to move the elements of the array a so that the tex2html_wrap_inline33 fraction comes first, then the tex2html_wrap_inline35 , and so on. For example, suppose k=9, tex2html_wrap_inline39 , tex2html_wrap_inline41 , and so on. We want the array reordered so that the top tex2html_wrap_inline43 of the numbers come first, then the second tex2html_wrap_inline43 , and so on. Within these tex2html_wrap_inline43 groups, the numbers need not be sorted. Find an algorithm based on the quick select idea that is better than sorting if 1 << k << n.
(from CLR, page 151) Give an tex2html_wrap_inline51 algorithm to merge k sorted lists into a single sorted list of length n. Hint: Make a heap of the largest element of each of the k sublists not yet merged into the final list.
Given an array of length n, not in order, we want to determine whether any two elements are the same. The algorithm must use only binary comparisons. Is it possible to do this using fewer than tex2html_wrap_inline61 comparisons or equality tests? We know that it is not possible to sort this list in fewer than tex2html_wrap_inline61 comparisons.

Jonathan Goodman
Wed Feb 4 18:44:43 EST 1998