// 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 ); } } } }