Programming Assignment 4 - Algorithm Animation

Data Structures & Algorithms, Spring 2010

Due Date

This assignment is due by 11:30 p.m. on Thursday, 4 May.

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 4 is Friday, 7 May at 11:30 p.m.. It is not possible to turn-in Assignment 4 after the absolute deadline.

Background

A sort is stable if the relative order of equal elements after the sort is the same as the relative order of equal elements before the sort. For example, given the point list
L = (5, 3), (1, 2), (1, 3), (4, 3)
a sort that orders points by increasing x coordinate and produces the point list
L’ = (1, 2), (1, 3), (4, 3), (5, 3)
is stable, while a sort that produces the list
L’ = (1, 3), (1, 2), (4, 3), (5, 3)
is not stable because (1, 3) appeared after (1, 2) in L but appears before (1, 2) in L’.

The Problem

Write the predicate isStableSort() accepting a sort and returning a boolean indicating whether or not the given sort is stable. isStableSort() should be a member of a class named SSP; SSP may contain any other methods you think necessary, and your solution may contain any other classes you think necessary.

isStableSort() is defined in the StableSortPredicate interface, which can be found in

/export/home/class/cs-305-503/pa4/StableSortPredicate.java
The sorting interface Sorter is defined in
/export/home/class/cs-305-503/pa4/Sorter.java

You can run your code with the jar file

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

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

When run, your code is run through some tests, and, if everything went as expected, the program exits with no output. Otherwise the program exits with an informative error message.

This page last modified on 12 April 2010.