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

    }

}