Q_Sort, an implementation of Quicksort on arrays.
Write a recursive version of quicksort for an array of
integers; you may use the book's implementation as a starting point if
you wish. Note, however, that the book's version is not complete, and
will leave some groups of integers out of order as a result of the
Cutoff parameter. Your code should read integers from
the standard input until an "end of file" character is encountered,
and then print the integers in sorted order. You may assume that
there will be no more than 10,000 inputs.
The main Q_Sort routine given in Figure 7.14 is
recursive. This means that, during the execution of
Q_Sort, a stack is maintained of recursive calls on
Q_Sort that remain to be executed. We refer to these
recursive calls as instantiations of Q_Sort.Each
instantiation is of the form Q_Sort(Left, Right), where
Left and Right are indices into the input
array A, with Left + 1 <= Right. The
size of the instantiation is defined as Left - Right +
1.
It is possible to construct examples in which the number of
instantiations on the stack becomes very large (can you determine how
large?). This is because the sizes of the instantiations on the stack
are very small. This problem can be fixed by changing the algorithm
so that it processes the small instantiations as early as possible, so
that the number of small instantiations cannot build up. Instead of a
stack, the modified algorithm maintains a linked list of the
instantiations remaining to be executed, and always selects one of
smallest size to be executed next. The second part of the assignment
is to construct such an implementation and verify its correctness.
You should extend your program to allow the user to choose which
algorithm to use, by adding a menu similar to the following:
Choose a sorting algorithm:
1. Recursive Quicksort
2. Iterative Quicksort
After the user selects an algorithm, the program should read the
numbers to be sorted as in the first part.
qsort and a
file input.txt containing input for your program. You
can redirect the input to your program so that it reads from
input.txt as follows:
qsort < input.txt
Similarly, you can send the output of your program to a file
output.txt by typing
qsort > output.txt
and combine the two options by typing
qsort < input.txt > output.txt
In order to make generating test data easier, I have written a program which takes an input N and generates a list with the integers 1..N in random order as output. The full path of the program (on the CSE instructional computers) is
~dfasulo/cse326/bin/genlist
g++ (compiler), emacs (editor),
make (compilation tool), and gdb (debugger).
Feel free to come to the TA's office hour for additional help with
these programs.
All users are strongly encouraged to use the skeletal makefile provided here to manage their programs. To use this file, save it with the name "makefile" in the same directory as your project source files, and follow the instructions in the file for filling in the necessary information.
Any student who does not have an account on the CSE instructional machines should request one by sending mail to support@cs.
turnin program on the
CSE instructional machines; type "man turnin" for more
details on how to use this program. Note that users of the makefile
above may type
make turnin
in order to submit their assignments, assuming that the information at
the top of the makefile is kept up-to-date.