What to submit and when:
The lab will be graded together with the next one. The grading criteria are posted with the next lab.
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 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:
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.
compareTo
increments the static counter by 1.
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. 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.