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 contributions of each person are.
- At the end of the lab each group should send me the results of their in-class work. Please indicate if this is your final submission.
- 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. Please use the subject "3501 Lab N", where N is the lab number.

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.

- Implement
`TestInteger`

and`quicksort`

method as described above. Test your implementation. - 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 using the mergesort and the other one using a quicksort. 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.

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.

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.