Subversion Repositories programming

// Written by Ira Snyder

import java.io.*;

import java.util.Random;

public class Test {

    private static int compCount, swapCount;

    private class Entry implements Comparable {

        public int x;

        public Entry( int x ) { this.x = x; }

        public int compareTo( Object o ) {

            compCount++;

            if( !(o instanceof Entry) ) throw new IllegalArgumentException();

            Entry y = (Entry)o;

            return this.x - y.x;

        }

        public Entry setEntry( int x ) {

            return new Entry(x);

        }

        public String toString() { return Integer.toString(x); }

    } //end Entry class

    public int getCompCount() { return compCount; }

    public int getSwapCount() { return swapCount; }

    public void resetCompCount() { compCount = 0; }

    public void resetSwapCount() { swapCount = 0; }

    //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.)

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

    }

    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

    }

    // 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 < 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

            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;

    }

    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("Number Swaps");

        return output.toString();

    }

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

    }

    public void testBubbleSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.BubbleSort(array);

        System.out.println( generateOutputLine("BubbleSort"));

    }

    public void testImprovedBubbleSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.ImprovedBubbleSort(array);

        System.out.println( generateOutputLine("Impr. BubbleSort"));

    }

    public void testSelectionSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.SelectionSort(array);

        System.out.println( generateOutputLine("SelectionSort"));

    }

    public void testInsertionSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.InsertionSort(array);

        System.out.println( generateOutputLine("InsertionSort"));

    }

    public void testShellSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.ShellSort(array);

        System.out.println( generateOutputLine("ShellSort"));

    }

    public void testMergeSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.MergeSort(array);

        System.out.println( generateOutputLine("MergeSort"));

    }

    public void testHeapSort( Entry[] array ) {

        resetSwapCount();

        resetCompCount();

        SortMethods.HeapSort(array);

        System.out.println( generateOutputLine("HeapSort"));

    }

    public void testQuickSort( Entry[] array ) { 

        resetSwapCount();

        resetCompCount();

        SortMethods.QuickSort(array);

        System.out.println( generateOutputLine("QuickSort"));

    }

    public void runTest( Entry[] array, String testHeader ) {

        //make 6 arrays

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

        System.out.println(testHeader);

        System.out.println( generateHeader() );

        testBubbleSort(array);

        testImprovedBubbleSort(arrayc1);

        testSelectionSort(arrayc2);

        testInsertionSort(arrayc3);

        testShellSort(arrayc4);

        testMergeSort(arrayc5);

        testHeapSort(arrayc6);

        testQuickSort(arrayc7);

    }

    public void test1() {

        Entry[] array = generateNumbers(512,0);

        String header = "Test 1: Array Length 512 Composed of Random Elements";

        runTest(array,header);

    }

    public void test2() {

        Entry[] array = generateNumbers(1024,0);

        String header = "Test 2: Array Length 1024 Composed of Random Elements";

        runTest(array,header);

    }

    public void test3() {

        Entry[] array = generateNumbers(2048,0);

        String header = "Test 3: Array Length 2048 Composed of Random Elements";

        runTest(array,header);

    }

    public void test4() {

        Entry[] array = generateNumbers(4096,0);

        String header = "Test 4: Array Length 4096 Composed of Random Elements";

        runTest(array,header);

    }

    public void test5() {

        Entry[] array = generateNumbers(1024,1);

        String header = "Test 5: Array Length 1024 Composed of Ascending Elements";

        runTest(array,header);

    }

    public void test6() {

        Entry[] array = generateNumbers(1024,2);

        String header = "Test 6: Array Length 1024 Composed of Descending Elements";

        runTest(array,header);

    }

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

    }

}