CSci 3501 Algorithms and Computability - Lab 3.
September 10. Due Wednesday, September 16 at 11:59pm
What to submit and when:
- All submissions are electronic: by e-mail to elenam at morris.umn.edu and CC to all lab partners. Please do not delete your e-mail from "Sent mail" or your mailbox until the end of the semester.
- When working on the lab, please comment your work so that it is clear what each person's contributions are.
- At the end of the lab each group must send me the results of their
in-class work. Please indicate if this is your final submission. Please use the subject "3501 Lab N", where N is the lab number.
- If your submission at the end of the lab time was not final, please send me(CC to the lab partner(s)) a final copy before the due time.
60 points (combined with lab 2). Grading criteria:
- Implementation of quicksort: 15 pts
- Correct setup (using Comparable, using mergesort, etc): 10 pts
- Test data and setup: 10 pts
- Randomized quicksort: 6 pts
- Median-of-three pivot: 6 pts
- Switching to insertion sort: 6 pts
- Observations and conclusions: 7 pts
Lab assignment
Continue working in groups from lab 2.
Overview and goals
In this lab we will continue studying efficiency of quicksort
(see http://en.wikipedia.org/wiki/Quicksort).
The goal is to develop and study approaches to improve efficiency of
quicksort. The approaches include a randomized
pivot selection, a median-of-three pivot selection to equalize the
split of elements, and use of
insertion sort when the array is nearly sorted. You will continue
experimenting with quicksort on different types of data (completely
random, ordered, partially ordered) and compare it to the pre-defined
mergesort in the number of comparisons. The goal is to learn practical
approaches to efficient algorithm implementation.
Note that other ways of speeding up quicksort may reduce the program's
running time by cutting down on recursive calls or by providing more
efficient memory usage. However, they do not reduce the number of
element comparisons, and thus will not be included in this lab.
Tasks
Use your implementation of quicksort and the testing code from the
previous lab. You will be using the same kind of data as in the lab
last week, i.e. arrays of 10,000 elements filled in as follows:
- Generated at random
- Sorted in increasing order (if this creates a stack overflow, use
1,000 elements)
- 10 sorted sequences of 1,000 elements each
- 100 sorted sequences of 100 elements each
Run all your tests (see below) 5 times on each of these sets.
You need to implement the modifications of quicksort listed
below. Please write a new copy of quicksort for each of the three
modifications. Then compare the results to the original quicksort and
to the mergesort (use the same data for all three sorting
algorithms). Make sure to test (for each modification!) that the
resulting array is sorted. Record the results (the number of
comparisons).
- Randomized quicksort: choose the pivot at random
at every step of the algorithm. For simplicity just exchange the
randomly chosen pivot with the element in the position r, this way you
don't have to rewrite your algorithm (see p. 179 for more
details).
- The median-of-three pivot selection: to select a
pivot, pick three subarray elements at random, then choose their
median as the pivot (see exercise 7-5 p. 188). Use
compareTo
for comparison of the three elements since
their comparison contributes to the total cost. Note that this
approach becomes less efficient as the array size decreases. Use a
threshold value k to switch to the usual pivot choice when the portion
of the array passed to quicksort is less than k. Try different values
of k and choose an optimal one (approximately).
- Switching to insertion sort at the end: when the
array is nearly sorted, stop the quicksort without finishing the
sorting, and then use insertion sort on the entire array to finish the
process. As in the previous problem,
choose a threshold subarray size to leave the array for the insertion
sort.
You will need to implement insertion sort (p. 18). Make sure to include the
comparisons made by the insertion sort into the total.
- Extra credit (after everything else is done): try any other optimizations that may be helpful. Note that beating the library version of merge sort in the number of comparisons may be impossible. The actual running time of your quicksort may be better than that of the merge sort. We will explore running time of sorting during the sorting competition later in the semester.
In case you are getting a Stack Overflow exception on sorted data:
You need to increase the stack size in
the JVM (Java Virtual Machine) which you can do by setting a JVM flag
in
Eclipse: http://stackoverflow.com/questions/2127217/java-stack-overflow-error-how-to-increase-the-stack-size-in-eclipse
You may submit one final version of the lab for labs 2 and 3 or
separate final submissions. In either case please make sure that all
questions are answered and clearly indicate whether you are submitting
the two labs separately or together.
CSci 3501
course web site.