CSE 326 - Autumn 2000

Practice/Review #7
These problems are NOT to be turned in.  They are practice problems
both to improve your understanding of the material and to prepare for
the final exam.

1. Consider an implementation of Quicksort which always uses the 
   middle element (left+right)/2 of the subarray being sorted as the 
   pivot.  Describe an input that gives the worst-case run time.

   Suppose the pivot is picked randomly.  Is there a input that always
   gives the worst-case run time?  Why or why not?

2. Let "XSort" be a mysterious sorting algorithm.  All you know about
   it is that it works by swapping elements that are no more than
   log(N) apart in the input, where N is the number of elements to be
   sorted.  What is a lower bound (omega) on XSort?  Is this bigger
   than the optimal lower bound for any comparison-based sorting
   algorithm?

3. Suppose you have an array of N elements containing only two
   distinct keys, 0 and 1.  Give an O(N) algorithm to rearrange the
   array so that all 0 elements preceed all 1 elements.  You many
   use only constant extra space.

	struct element{
		int key;
		string data; }

4. Suppose you have a text file containing names in the following
   format:

columns 1-20: first name and middle name or initial if any
columns 21-40: last name

For example:
John J             Smith
Henry              Kautz
George Wilfred     Bush
John               Smith

You want to sort the file by last name then first name, e.g.

George Wilfred     Bush
Henry              Kautz
Albert             Smith
John               Smith
John J.            Smith

You are given a "sort" command that sorts lines on the basis of the
string that appears in a given range of columns: e.g.,
	sort +21 -40 < infile > outfile
will sort just by last names.

(1) How can you sort the data as specified if the sort command is
    stable? 

(2) Suppose you discover that the sort command is not stable.  Then
    what can you do (without writing another sort command)?