HW#3 --- last modified February 07 2019 04:29:43..
Solution set.
Due date: Mar 17
Files to be submitted:
Hw3.zip
Purpose: Experiment with quicksort and radix sort variants
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO4 -- Use advanced sorting techniques (radix sort, heapsort, mergesort, quicksort).
Specification:
This project consists in the development of four programs and a write-up of experiments conducted with these programs.
The first program is a random string generator. The grader will compile this program as the command line using:
javac RandomStringGenerator.java
The program will then be run with a line like:
java RandomStringGenerator prob num_strings
For example,
java RandomStringGenerator .1 5
The prob value is used to control the length of the string, the num_strings value controls the number of strings generated.
To generate a string, your program should choose uniformly at random a character amongst a,b,c,...,z. This is the first character of the
string. Then it should choose a float value uniformly at random between 0 and 1. If this is less than prob (in this example, 0.1) it should continue to build the string, otherwise,
it should stop building the string and output it to stdout (one string/line). If it continues building the string it repeats the process just
described: It picks a random character amongst a,b,c,...,z appends it to the string, then picks a random float between 0 and 1, etc. Example output
for the above statement might be:
f
t
yr
q
dar
We could of course use a command-line redirect to send the output to a file. The second program you will write for this homework is FileQuickSort.java. It will be compiled from the command line with a line like:
javac FileQuickSort.java
and it will be run with a line like:
java FileQuickSort filename.txt pivot_pos
Here filename.txt is an arbitrary name of a file containing strings over the alphabet a-z, one string per line. So if blah.txt were a file containing:
adsgfa
hfgfh
jfgiouterhd
fhgj
slkjfjhkgfdsf
I could run FileQuickSort on it using:
java FileQuickSort blah.txt 3
FileQuickSort should implement a variant of quicksort with pivots chosen according to pivot_pos. That is, whenever the quicksort makes a recursive call to quicksort a subarray `A`, `p`, `r`, it chooses as the pivot `min(p+text(pivot_pos), r)`. The documentation at the start of the file should clearly indicate the line number where your code for this lives. The output of FileQuickSort is the same lines input but in sorted order, followed by a time in milliseconds to do the sorting. For the example above,
adsgfa
fhgj
hfgfh
jfgiouterhd
slkjfjhkgfdsf
123 milliseconds
The next program I want you to write is FileQuickInsertSort.java. Again, it will be compile with a line like:
javac FileQuickInsertSort.java
and run with a line like:
java FileQuickInsertSort filename.txt insert_threshold
For example,
java FileQuickInsertSort blah.txt 5
This variant on quicksort uses a randomly chosen pivot from amongst the elements of the sub-array that are being sorted, unless
the subarray to be sorted has size less than insert_threshold, in which case, rather than do quicksort on the subarray, it just runs insertion sort on it. The comments
on the top of this file should clearly indicate where to look for this modification. The output of this program is again the sorted strings each on a line followed
by the run-time.
The last program I want you to implement is FileModifiedRadixSort.java. It will be compile with a line like:
javac FileModifiedRadixSort.java
and run with a line like:
java FileModifiedRadixSort filename.txt
For example,
java FileModifiedRadixSort blah.txt
This program also takes the strings in filename.txt or blah.txt and outputs them in sorted order followed by the time in milliseconds. To do the sorting it should
make an initial pass through the strings and find the longest string. It should then pretend all the strings have this length and do radix sort. Sorting thus would proceed
from the last column to the first column. If a string does not have a column `i` because it is too short, we pretend that it has a value @ for that column and that @ is earlier in
the alphabet than the letter a. When we write the final output we write the original strings (no @ signs).
Once you have your four programs I want you to do some experiments with them. I would like to use RandomStringGenerator to generate 10 files where the prob takes on the different values
0.9, 0.91, 0.92, ... 0.99 and the number of strings to sort is from 5000. Then I want you to generate 10 more files where the prob is 0.95 and the number of strings to sorts is 1000, 2000, 3000, ..., 10000. For FileQuickSort I want you to choose the pivot position to be 2, for FileQuickInsertSort I want you to choose the insert_threshold to be 7. Then I want you to run your three sorters using these parameters on each of these test files. I would like you to plot your results on graphs and write a page report summarizing what you found out. Put your report with graphs in a file Hw3.pdf in your submitted ZIP file.
Point Breakdown
SJSU CS Department guidelines for Java followed in each of the four programs (graded 0 more than three items on guidelines missed in any file, 0.5 any items
missed, 1 no defects) | 1pt
|
RandomStringGenerator operates as described | 1pt
|
FileQuickSort operates as described (0.5 reads in text file, 0.5 implements quicksort correctly, 0.5 partition uses pivot as described above, 0.5 output as described) | 2pts
|
FileQuickInsertSort operates as described (0.5 implements quicksort correctly, 0.5 pivot randomly chosen, 0.5 switches to insertion sort at threshold as described, 0.5 file reading and output as described) | 2pts
|
FileModifiedRadixSort operates as described (0.5 reads in text file, 0.5 implements radix sort correctly, 0.5 handles different length strings as described above, 0.5 output as described) | 2pts
|
Graphs generated for the experiments described above | 1pt
|
Write-up of experiment | 1pt
|
Total | 10pts |
|