CSci 3501 Algorithms and Computability - Lab 3.

September 8. Due Wednesday, September 14 at 11:59pm

What to submit and when:

60 points (combined with lab 2). Grading criteria:

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 make the quicksort split data as evenly as possible. The approaches include a randomized pivot selection, a median-of-three pivot selection, 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:

  1. Generated at random
  2. Sorted in increasing order (if this creates a stack overflow, use 1,000 elements)
  3. 10 sorted sequences of 1,000 elements each
  4. 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).

In case you are getting a Stack Overflow exception: numbers in increasing order may generate a stack overflow because there are 10000 calls (that's the worst case of quicksort when there is one call per element) which is more than the default stack size. 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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.