Fundamental Algorithms, Spring 1998

Assignment 3. Heapsort and quicksort.

Given February 4, due Monday, February 16.

1.

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 and we want to move the elements of the array a so that the fraction comes first, then the , and so on. For example, suppose k=9, , , and so on. We want the array reordered so that the top of the numbers come first, then the second , and so on. Within these 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.

2.

(from CLR, page 151) Give an 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.

3.

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 comparisons or equality tests? We know that it is not possible to sort this list in fewer than comparisons.

• About this document ...