Programming Assignment 2

Three Sorting

Data Structures & Algorithms, Spring 2010

Due Date

This assignment is due by 11:30 p.m. on Tuesday, 23 March.

See the assignment turn-in page (last modified on 23 February 2010) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 2 is Friday, 26 March at 11:30 p.m.. It is not possible to turn-in Assignment 2 after the absolute deadline.

Background

An array containing only the values 1, 2, and 3 is three sorted if all occurrences of 2s appear after any occurrence of 1s and all occurrences of 2s appear after any occurrence of 2s. For example, the array 

[ 1, 1, 2, 3, 3, 3 ]

is three sorted, while the array 

[ 3, 1, 2, 3, 3, 1 ]

is not.

The Problem

Implement two methods to three sort an array; one of the methods should take O(n2) time, and the other should take O(n) time. The method signatures are given in
/export/home/class/cs-305-503/pa2/ThreeSorters.java

The methods should be part of a class called ThreeSorting. ThreeSorting may contain other methods, although other methods will be ignored by the assignment code, and you may define any other classes you think necessary.

Any code you write for three-sorting should be your own; you should not rely on any Java library algorithms to implement the three-sorters.

You can test your code by running the jar file

/export/home/class/cs-305-503/pa2/pa2.jar
using the command 

$ java -classpath /export/home/class/cs-305-503/pa2/pa2.jar:. main options

If no output results, then everything worked; otherwise error messages are written to std-err. options may be one or more of the following:

For example, the command 

$ java -classpath /export/home/class/cs-305-503/pa2/pa2.jar:. main -v -p

prints informative messages and, assuming no errors occurred, plots the timing data:

example timing graphs

This page last modified on 14 March 2010.