CSci 3501 Algorithms and Computability - Lab 2.

September 2. Due Wednesday, September 8 at 11:59pm

What to submit and when:

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 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. 171). 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:

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:

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/2127217/java-stack-overflow-error-how-to-increase-the-stack-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.

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.