<strong>
<br><a href="http://www.unlv.edu/">University of Nevada Las Vegas </a>
<br><a href="http://www.egr.unlv.edu/"> Howard R. Hughes College of
Engineering </a>
<br><a href="http://www.cs.unlv.edu/"> School of Computer Science </a><br>
<a href="http://www.cs.unlv.edu/~larmore"> My Home Page</a><br> </strong>
UNLV CS Spring 2007 Assignment 6
CS 302 Assignment 6
Due date: Tuesday, March 6, 2007, midnight.
All programming assignments must be
submitted electronically.
Submit them to the graduate assistant,
James Oravec,
on or before the due date.
All written assignments must be handwritten
(not typed or printed from a
computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4
paper. Write your name on each sheet, and do not fold the pages or crimp the
corners. (You may use a paper clip or a staple.)
Quicksort a list of items.
-
The input of your program will be a file consisting of lines, which each
line consists of some text followed by an integer, which we call the
key. You may assume that there is at least one space between
the text and the number. The output of your program will be a file consisting
of same lines, sorted by key.
For example, if the input file is this:
Joe 3
Mary Lou 7
Aaron 6
Then your output file should be this:
Joe 3
Aaron 6
Mary Lou 7
-
Read the items from the standard input file into an array of an appropriate type.
-
You may assume that no input line has more than 80 characters, and that there
are no more than 1000 input lines.
-
Use an
in situ implementation of
quicksort
to sort the array.
-
Maintain a comparison counter, a variable that is initialized
to be zero and which increments each time two keys are compared.
-
Your output should consists of a list of the same items, sorted by key,
together with an analysis stating how many items there were and how many
comparisons were made.
-
Here is a file to practice on.
-
Here is a smaller file to practice on.
-
Here is a a larger file to practice on.
-
If, in your analysis, it does not look like the number of comparisons
is O(n log n), you might be doing something wrong, in which case, you
should try to fix the problem.