What to submit and when:

- All submissions are electronic: by e-mail to elenam at morris.umn.edu 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.

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:

- 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 Math.random. 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.