/** * Example of a bad algorithm --- one that succeeds, but very slowly. * Sort an array by successively shuffling it and seeing whether it is * in order. * * By checking before shuffling, this takes O(n) time as its best case. * * Unfortunately, it tends to be O( exponential(n) ) time otherwise. * * Perpetrator: Timothy Rolfe */ public class BadSort { // Generator needed both in shuffle and in main static private java.util.Random generator = new java.util.Random(); // Count number of calls to validate static private long nCalls; // Note: this code uses the following methods, described by their names: // boolean validate(Comparable[]) // In other words, ? in order ? // void shuffle(Comparable[]) public static void main ( String[] args ) { for ( int size = 2; size < 13; size ++ ) { Integer[] array = new Integer[size];; long start; // Random contents in the array for ( int j = 0; j < size; j++ ) array[j] = new Integer ( generator.nextInt(32768) ); start = System.currentTimeMillis(); nCalls = 0; // Validate counter to zero // Shuffle the array until it comes into order while ( !validate (array) ) // I.e, NOT in order shuffle(array); System.out.println ( ( size < 10 ? " " : "" ) + size + " items: " + (System.currentTimeMillis()-start) + " msec, " + nCalls + " validation calls."); } } // Standard array swap method static private void swap ( Comparable[] array, int p, int q ) { Comparable temp = array[p]; array[p] = array[q]; array[q] = temp; } // Randomize the contents of the array static private void shuffle ( Comparable[] array ) { int lim = array.length; // First, length, then subscript of last while ( lim > 1 ) { int item = generator.nextInt(lim); lim--; // Form subscript of last swap ( array, item, lim ); } } // Check whether the array is in order static private boolean validate ( Comparable[] array ) { nCalls++; // Count up calls to validate if ( array.length < 2 ) return true; // Necessarily in order for ( int k = 1; k < array.length; k++ ) if ( array[k-1].compareTo(array[k]) > 0 ) return false; // I.e., out of order return true; // None out of order, so . . . } } /* Specimen run: Running on wyoming.ewu.edu trolfe@wyoming CScD-326 \$ javac BadSort.java trolfe@wyoming CScD-326 \$ java BadSort 2 items: 0 msec, 1 validation calls. 3 items: 0 msec, 1 validation calls. 4 items: 0 msec, 15 validation calls. 5 items: 1 msec, 137 validation calls. 6 items: 6 msec, 561 validation calls. 7 items: 11 msec, 5449 validation calls. 8 items: 51 msec, 28348 validation calls. 9 items: 163 msec, 82177 validation calls. 10 items: 7227 msec, 3231858 validation calls. 11 items: 124614 msec, 49692781 validation calls. 12 items: 319326 msec, 115759560 validation calls. */