CSci 3501 Algorithms and Computability - Lab 2.

August 31st. Due Wednesday, September 6 at 11:59pm

What to submit and when:

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 the standard Java algorithms for objects (Tim Sort) 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 an algorithm known as Tim Sort which is a specifically designed 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:

Tasks

Your task is to sort the same arrays using the standard Java sorting (Tim Sort) 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/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.

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.