What to submit and when:
Work in pairs.
In this lab you will study the efficiency of mergesort and quicksort (see http://en.wikipedia.org/wiki/Quicksort) for different types of data (such as completely random, ordered, partially ordered). The 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.
You will use a predefined method sort that implements mergesort
. Please read the method description carefully.
You will need to write your own implementation of quicksort
. Your quicksort may take an array of TestInteger
type (see below) according to the algorithm in the book. Use compareTo
method to compare elements.
In order to count the number of comparisons you need to create your own class TestInteger
that has an integer field value
for comparison and a static long
field counter
to count the number of comparisons performed on all TestInteger
objects. TestInteger must implement Comparable
interface (or Comparable<TestInteger>
if you are using generics).
The compareTo
method of TestInteger
must return the result of comparison of the values of the two TestInteger
objects according to the specification in the Comparable interface: see compareTo. In addition it must increment the static counter by 1.
When generating arrays to be sorted, create two arrays and insert the same elements in both in the same order. Sort one array using mergesort
and the other one using quicksort
. Make sure to record and reset the TestInteger
counter between the two sortings.
To make sure that quicksort works correctly, write a method isSorted
to check if an array is sorted. When performing measurements, record the counter value before you run isSorted
method since it would change the counter.
TestInteger
and quicksort
method as described above. Test your implementation. For each kind of data, which of the two algorithms performs better? Submit your program, the results of measurements, and noted on your observations.
Next week the lab will focus on improvements to quicksort.