CIS-610 Data Structures and Algorithms

Home Work #7							Due:	11/11/1999


1. Rewrite the routine bubble so that successive passes go in opposite directions.

2. A sort by counting is performed as follows. Declare an array count and set count[j] to the number of elements that are less than x[j]. Then place x[j] in position count[j] of an output array. (However, beware of the possibility of equal elements.). Write a routine to sort an array x of size n using this method.

3. Rewrite the routines for bubble sort and the quick sort as presented so that a record is kept of the actual number of comparisons and the actual number of interchanges made.

4. A tournament is an almost complete strictly binary tree in which each nonleaf contains the larger of the two elements in its two sons. Thus the contents of a tournament's leaves completely determine the contents of all its nodes. A tournament with n leaves represents a set of n elements.


a. Develop an algorithm pqinsert(t, n, elt) to add a new element elt to a tournament containing n leaves represented implicitly by an array t.

b. Develop an algorithm pqmaxdelete(t, n) to delete the maximum element elt from a tournament containing n by replacing the leaf containing the maximum element with a dummy value smaller than any possible element (ex. -1 for a tournament  of  non-negative integers) and then readjusting all values in the path from that leaf to the root.

5. Write an algorithm for a routine merge(x, lb1, ub1, ub2) that assumes that x[lb1] through x[ub1] and x[ub1 + 1] through x[ub2] are sorted and merges the two into x[lb1] through x[ub2].

6. Write a routine that sorts a file by first applying the radix sort to the most significant r digits (where r is a given constant) and then uses straight insertion to sort the entire file. This eliminates the excessive passes on low-order digits that may not be necessary.