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