What to submit and when:
Work in pairs.
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.
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 takes an array of TestInteger
type (see below) according to the algorithm in the book (p. 146). 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:
Comparable<TestInteger>
interfacevalue
(that's what compareTo
compares)long
field counter
to count the number of comparisons performed on all TestInteger
objects.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.
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:
TestInteger
and quicksort
method as described above. Test your implementation using isSorted method. 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.