CSci 3501 Algorithms and Computability - Lab 2.

September 1. Due Wednesday, September 9 at 11:59pm

What to submit and when:

• All submissions are electronic: by e-mail to 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.

The lab will be graded together with the next one. The grading criteria are posted with the next lab.

Lab assignment

Work in pairs.

Overview and goals

In this lab you will study efficiency of mergesort and quicksort (see http://en.wikipedia.org/wiki/Quicksort) for different types of data (completely random, ordered, partially ordered). Efficiency of the algorithms is measured in the number of comparisons. Your program will call both sorting methods on the same data and measure the number of comparison operations performed by each sorting algorithm. The goal is to observe and analyze practical aspects of sorting. The lab also helps you learn testing methodology for algorithms analysis.

Technical details

You will use a predefined method sort that implements a `mergesort` modified to produce high efficiency on partially sorted arrays. Note that this is a static method of a class `Arrays` which works on arrays of objects.

You will need to write your own implementation of `quicksort` according to the algorithm in the book (p. 171). Make sure that you implement the in-place quicksort given in the book (i.e. your algorithm shouldn't create additional arrays). Your quicksort takes an array of `TestInteger` type (see below). Use `compareTo` method to compare elements, do not use <. Try to minimize the number of comparisons.

In addition please write a method `isSorted` that takes an array of `TestInteger`s and returns "true" if it is sorted and "false" otherwise. Use this method to test your quicksort.

In order to count the number of comparisons you need to create your own class `TestInteger` as follows:

• it implements `Comparable<TestInteger>` interface
• it has an integer field `value` (that's what `compareTo` compares)
• it has a static `long` field `counter` to count the number of comparisons performed on all `TestInteger` objects.
• The `compareTo` method returns the result of comparison of the `value` field of "this" `TestInteger` and the parameter `TestInteger` according to the specification in the Comparable interface: see compareTo.
Before performing a comparison, `compareTo` increments the static counter by 1.
• you will need to write methods to get the counter and to reset it to 0

Your task is to sort the same arrays using the standard mergesort and your own quicksort and measure the number of comparisons for each sorting using the static counter in `TestInteger`. Specifically:

• Implement `TestInteger` and `quicksort` method as described above. Test your implementation using isSorted method.
• Generate 10,000 random TestIntegers in the range from 1 to 1,000,000 and put them (in the same order) into two arrays. Use Java random number generator Random. Make sure to use only one Random object in your program - create it in the very beginning outside of any loops. Sort one array using the predefined mergesort, and the other one using a quicksort. Make sure to record the value of the counter and reset it between the sortings. Also be careful not to include comparisons from isSorted into your totals.
Run the program 5 times measuring the time to sort the two arrays (separately) in the number of comparisons. Record your results.
• Repeat the sorting, but instead of random elements use the arrays where elements are stored in increasing order. Record the results.
• Repeat the measurements for arrays that consist of 10 sorted sequences of 1,000 elements each (randomly choose the starting number in each sequence). Record the results of 5 measurements.
• Repeat the measurements for arrays that consist of 100 sorted sequences of 100 elements each (randomly choose the starting number in each sequence). Record the results of 5 measurements.

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/15313393/how-to-increase-heap-size-in-eclipse

For each kind of data, which of the two algorithms performs better? Submit your program, the results of measurements, and your observations.

Next week the lab will focus on improvements to quicksort.

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.