// This program is the core of an example computer science experiment. The
// experiment tests the prediction that Selection Sort will take more time
// as the array it has to sort gets longer. This prediction follows from
// the observation that Selection Sort's two loops each repeat more often
// to sort a longer array, and therefore that the algorithm executes more
// steps to sort longer arrays.
//
// This program encapsulates Selection Sort in a "SortableArray" class,
// which provides convenient ways to initialize an array and display its
// contents, as well as the core sort method. The arrays that this class
// represents are simply arrays of integers. They have room for some maximum
// number of integers, but needn't always be full. Therefore it is helpful
// to distinguish a sortable array's current size from its maximum size.
// In full detail, the class provides the following to its clients:
//
// o A constructor that takes a single integer, the maximum array size,
// as its parameter. The constructor initializes a SortableArray able
// to contain up to that size, and fills it with integers in descending
// order (exactly the opposite of the order that the sort produces).
// Preconditions: The requested size is greater than 0.
// Postconditions: The SortableArray contains the requested number of integers,
// in decreasing order. The SortableArray's current size is equal to
// the parameter.
//
// o reset, a message that takes an integer as its parameter, and replaces
// the contents of a SortableArray with that many integers in
// descending order. This message has no return value.
// Preconditions: The parameter is greater than or equal to 0, and
// less than or equal to the size provided to the constructor that
// initialized this SortableArray.
// Postconditions: The SortableArray's current size equals the parameter, and
// the array contains that many integers, in descending order.
//
// o getSize, a parameterless message that returns a SortableArray's current size.
//
// o display, a parameterless message that causes a SortableArray to
// print its contents to standard output. This message has no return
// value.
//
// o sort, a parameterless message that causes a SortableArray to sort
// itself into ascending order. This message has no return value.
// Postconditions: The array contains the same integers it contained
// before receiving the "sort" message, but each (except the last)
// is less than or equal to the one immediately after it in the array.
//
// In addition to these features for clients, the SortableArray class also
// provides...
//
// o A main method that carries out the experiment, i.e., sorts a variety
// of SortableArrays and reports how long the sorts take.
// History:
// April 2001 -- Created by Doug Baldwin.
// June 2003 -- converted to Java By Greg Scragg and Doug Baldwin.
// Copyright (C) 2008 by Cengage Learning.
class SortableArray {
// Internally, a SortableArray maintains its array of integers and
// current size:
private int[] theArray;
private int currentSize;
// The constructor for SortableArrays. This simply allocates the array,
// and fills it with integers in decreasing order.
public SortableArray ( int n ) {
theArray = new int[n];
this.reset( n );
}
// The reset method. This places integers between n and 1, in
// decreasing order, into the first n elements of the array, then
// records the current size as being n.
public void reset( int n ) {
for ( int i = 0; i < n; i++ ) {
theArray[i] = n - i;
}
currentSize = n;
}
// The getSize method.
public int getSize() {
return currentSize;
}
// The "display" method for SortableArrays. This simply loops through
// the array, printing each element.
void display() {
for ( int i = 0; i < currentSize; i++ ) {
System.out.println( theArray[i] );
}
}
// The "sort" method for SortableArrays. This is a completely standard
// selection sort.
void sort() {
for ( int current = 0; current < currentSize-1; current++ ) {
int minSoFar = current;
for ( int minSeeker = current+1; minSeeker < currentSize; minSeeker++ ) {
if ( theArray[minSeeker] < theArray[minSoFar] ) {
minSoFar = minSeeker;
}
}
int temp = theArray[current];
theArray[current] = theArray[minSoFar];
theArray[minSoFar] = temp;
}
}
// The main program creates several SortableArray objects and measures
// how long each takes to sort itself.
public static void main(String args[]) {
System.out.println( "Start" );
test();
System.out.println( "Stop" );
}
// The test method actually carries out the experiment. Specifically, it creates a
// SortableArray of the largest size to be used in the experiment, then loops through
// a series of array sizes, resetting the array to each size and sorting it several
// times. This method measures and reports how long each sort takes.
private static void test() {
final int[] sizes = { 1000, 2000, 4000, 8000, 16000, 32000, 64000 }; // The sizes to sort
final int subjects = 20; // Number of tests for each size
SortableArray subjectArray = new SortableArray( sizes[ sizes.length-1 ] ); // The array to time sorts in
// The first sort is likely to take an unusually long time, due, for example, to
// just-in-time compilation. So do a first sort that's not timed to get past this.
subjectArray.sort();
// Now start doing and timing the runs we're really interested in:
for( int arrayCount = 0; arrayCount < sizes.length; arrayCount++) { // Test each size
System.out.println("Sorting a " + sizes[arrayCount] + " element array:");
for ( int i = 0; i < subjects; i++ ) { // Make several tests
subjectArray.reset( sizes[arrayCount] );
long startTime = System.currentTimeMillis();
subjectArray.sort();
long endTime = System.currentTimeMillis();
long time = endTime - startTime;
System.out.println( "\t" + time );
}
}
}
}