CSci 3501 Algorithms and Computability - Lab 2.

September 1. Due Wednesday, September 7 at 11:59pm

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.

Grading

The lab will be graded together with the next one. The grading criteria are posted with the next lab.

Lab assignment

Work in pairs.

Overview and goals

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.

Technical details

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 TestIntegers 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

Tasks

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.

CSci 3501 course web site.