Subversion Repositories programming

// Written by Ira Snyder
// Project #5
// Due Date: 12-03-2004
// People Helped: Allen Oliver
// License: Public Domain (added 07-11-2005)

import java.io.*;
import java.util.Random;

public class Test {
    //some variables to keep track of compares and swaps
    private static int compCount, swapCount;
    
    //the class Entry, which stores int's
    private class Entry implements Comparable {
        public int x; //the data
        
        //constructor
        public Entry( int x ) { this.x = x; }
        
        //method to compare this to another object
        //returns 0 if they are equal, >0 if this is bigger,
        //and <0 if o is bigger
        public int compareTo( Object o ) {
            compCount++;
            if( !(o instanceof Entry) ) throw new IllegalArgumentException();
            
            Entry y = (Entry)o;
            return this.x - y.x;
        }
        
        //change the value of the current Entry
        public Entry setEntry( int x ) {
            return new Entry(x);
        }
        
        //print the Entry
        public String toString() { return Integer.toString(x); }

    } //end Entry class
    
    //get the private variables
    public int getCompCount() { return compCount; }
    public int getSwapCount() { return swapCount; }
    
    //reset compares and swaps
    public void resetCompCount() { compCount = 0; }
    public void resetSwapCount() { swapCount = 0; }
    
    //increment the swapcount variable
    public static void incSwapCount() { swapCount++; }
    public static void incSwapCount( int increaseBy ) { swapCount += increaseBy; }

    //this is the only way a swap method can be made in java.
    //the usual C++ (and others) way of using pointers is not
    //possible in java. (I've come up with a very solid
    //explanation of this. See me if you want to know.)
    //
    //this method adds to swapcount, and should be called for swaps
    //during a test run
    public static void swap( Object[] array, int posA, int posB ) {
        Object temp = array[posB];  // temp = B
        array[posB] = array[posA];  // B = A
        array[posA] = temp;         // A = temp
        swapCount++;
    }
    
    //method to print the entire array of type Object
    public void printArray( Object[] array, PrintStream ps ) {
        int i=0;
        for( i=0; i<array.length-1; i++ ) { System.out.print(array[i] + ", "); }
        System.out.println(array[i]); //print the last element
    }
    
    //method to generate an array of Entry's. It can generate arrays of
    //any size, and will generate then with different ordering of numbers
    //inside the array
    //
    // howMany should be how many numbers you want to generate
    // order: 0 = random
    //        1 = ascending
    //        2 = descending
    public Entry[] generateNumbers( int howMany, int order ) {
        Random generator = new Random();
        Entry[] answer = new Entry[howMany];
        
        //if order is a bad value, throw an Exception
        if( order < 0 || order > 3 ) throw new IllegalArgumentException();
        
        for( int i=0; i<howMany; i++ ) {
            //I deemed random int's from 0 to 10239 to be a good test
            //so I used these instead of the default, which is from
            // -MAX_INT to +MAX_INT
            if( order == 0 ) { answer[i] = new Entry(generator.nextInt(10240)); }
            else if( order == 1) { answer[i] = new Entry(i); } //ascending
            else if( order == 2 ){ answer[i] = new Entry(howMany-i-1); } //descending
            else { answer[i] = new Entry(1); } //set all to 1.0
        }
        
        return answer;
    }
    
    //method to generate a nice header for the program's output
    //I did this to eliminate duplicate code
    private String generateHeader() {
        StringBuffer output = new StringBuffer("Method");
        StringBuffer spaces = new StringBuffer();

        for( int i=output.length(); i<20; i++ ) { spaces.append(" "); }
        output.append(spaces);
        output.append("Number Compares");
        
        spaces = new StringBuffer();
        for( int i=output.length(); i<48; i++ ) { spaces.append(" "); }
        output.append(spaces);
        output.append("Data Movements");

        return output.toString();
    }
    
    //method to generate a properly spaced output line, which is used
    //to output the type of sort method, the number of swaps, and the
    //number of compares
    //
    //this prints out the number of swaps and compares that are stored
    //at the time that this is called
    private String generateOutputLine( String name ) {
        StringBuffer output = new StringBuffer(name); //put the name
        StringBuffer spaces = new StringBuffer();

        for( int i=output.length(); i<20; i++ ) { spaces.append(" "); }
        output.append(spaces);
        output.append(getCompCount()); //appends the current number of comps

        spaces = new StringBuffer();
        for( int i=output.length(); i<48; i++ ) { spaces.append(" "); }
        output.append(spaces);
        output.append(getSwapCount()); //appends the current number of swaps

        return output.toString();
    }
        
    //method to run BubbleSort and print the output
    public void testBubbleSort( Entry[] array ) {
        resetSwapCount(); //resets the counting variables
        resetCompCount();
        
        SortMethods.BubbleSort(array); //sort the array
        
        //print the output line
        System.out.println( generateOutputLine("BubbleSort"));
    }
    
    //method to run ImprovedBubbleSort and print the output
    public void testImprovedBubbleSort( Entry[] array ) {
        resetSwapCount(); //resets the counting variables
        resetCompCount();
        
        SortMethods.ImprovedBubbleSort(array); //sort the array

        //print the output line
        System.out.println( generateOutputLine("Impr. BubbleSort"));
    }
    
    //method to run SelectionSort and print the output
    public void testSelectionSort( Entry[] array ) {
        resetSwapCount(); //reset counting variables
        resetCompCount();
        
        SortMethods.SelectionSort(array); //sort the array
        
        //print the output line
        System.out.println( generateOutputLine("SelectionSort"));
    }
    
    //method to run InsertionSort and print the output
    public void testInsertionSort( Entry[] array ) {
        resetSwapCount(); //reset counting variables
        resetCompCount();

        SortMethods.InsertionSort(array); //sort the array

        //print the output line
        System.out.println( generateOutputLine("InsertionSort"));
    }
    
    //method to run ShellSort and print the output line
    public void testShellSort( Entry[] array ) {
        resetSwapCount(); //reset counting variables
        resetCompCount();

        SortMethods.ShellSort(array); //sort the array

        //print the output line
        System.out.println( generateOutputLine("ShellSort"));
    }

    //method to run the MergeSort and print the output line
    public void testMergeSort( Entry[] array ) {
        resetSwapCount(); //reset counting variables
        resetCompCount();

        SortMethods.MergeSort(array); //sort the array

        //print the output line for MergeSort
        System.out.println( generateOutputLine("MergeSort"));
    }

    //method to run the HeapSort and print the output line
    public void testHeapSort( Entry[] array ) {
        resetSwapCount(); //reset counting variables
        resetCompCount();

        SortMethods.HeapSort(array); //sort the array

        //print the output line for HeapSort
        System.out.println( generateOutputLine("HeapSort"));
    }

    //method to run QuickSort on the array, and print the output line
    public void testQuickSort( Entry[] array ) { 
        resetSwapCount(); //reset counting variables
        resetCompCount();

        SortMethods.QuickSort(array); //sort the array

        //print the output line for QuickSort
        System.out.println( generateOutputLine("QuickSort"));
    }
    
    //a generic method that will print out the header given to it
    // as a parameter, then run the suite of tests on the given array
    public void runTest( Entry[] array, String testHeader ) {
        //make 6 arrays (copies)
        Entry[] arrayc1 = new Entry[array.length];
        Entry[] arrayc2 = new Entry[array.length];
        Entry[] arrayc3 = new Entry[array.length];
        Entry[] arrayc4 = new Entry[array.length];
        Entry[] arrayc5 = new Entry[array.length];
        Entry[] arrayc6 = new Entry[array.length];
        Entry[] arrayc7 = new Entry[array.length];
        
        //fill the copies from the original
        System.arraycopy(array,0,arrayc1,0,array.length);
        System.arraycopy(array,0,arrayc2,0,array.length);
        System.arraycopy(array,0,arrayc3,0,array.length);
        System.arraycopy(array,0,arrayc4,0,array.length);
        System.arraycopy(array,0,arrayc5,0,array.length);
        System.arraycopy(array,0,arrayc6,0,array.length);
        System.arraycopy(array,0,arrayc7,0,array.length);
        
        //print both headers
        System.out.println(testHeader);
        System.out.println( generateHeader() );

        //run each test on one copy of the original array
        testBubbleSort(array);              //BubbleSort
        testImprovedBubbleSort(arrayc1);    //ImprovedBubbleSort
        testSelectionSort(arrayc2);         //SelectionSort
        testInsertionSort(arrayc3);         //InsertionSort
        testShellSort(arrayc4);             //ShellSort (AKA Comb Sort)
        testMergeSort(arrayc5);             //MergeSort
        testHeapSort(arrayc6);              //HeapSort
        testQuickSort(arrayc7);             //QuickSort
    }

    //run the test for 512 random elements
    public void test1() {
        Entry[] array = generateNumbers(512,0);
        String header = "Test 1: Array Length 512 Composed of Random Elements";
        runTest(array,header);
    }
    
    //run the test for 1024 random elements
    public void test2() {
        Entry[] array = generateNumbers(1024,0);
        String header = "Test 2: Array Length 1024 Composed of Random Elements";
        runTest(array,header);
    }

    //run the test for 2048 random elements
    public void test3() {
        Entry[] array = generateNumbers(2048,0);
        String header = "Test 3: Array Length 2048 Composed of Random Elements";
        runTest(array,header);
    }
    
    //run the test for 4096 random elements
    public void test4() {
        Entry[] array = generateNumbers(4096,0);
        String header = "Test 4: Array Length 4096 Composed of Random Elements";
        runTest(array,header);
    }

    //run the test for 1024 Ascending elements (0,1,2 ... 1023,1024)
    public void test5() {
        Entry[] array = generateNumbers(1024,1);
        String header = "Test 5: Array Length 1024 Composed of Ascending Elements";
        runTest(array,header);
    }

    //run the test for 1024 Descending elements (1024,1023 ... 2,1,0)
    public void test6() {
        Entry[] array = generateNumbers(1024,2);
        String header = "Test 6: Array Length 1024 Composed of Descending Elements";
        runTest(array,header);
    }
    
    //run the test for 1024 elements that all have the value 1.0
    public void test7() {
        Entry[] array = generateNumbers(1024,3);
        String header = "Test 7: Array Length 1024 Composed of Elements of value 1.0";
        runTest(array,header);
    }
}