Subversion Repositories programming

Rev

Rev 53 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 53 Rev 54
Line 1... Line 1...
1 
// Written by Ira Snyder
 1 
// Written by Ira Snyder
2 
 
 2 
 
3 
import java.io.*;
 3 
import java.io.*;
- 
 
 4 
import java.util.Random;
4 
 
 5 
 
5 
public class Test {
 6 
public class Test {
6 
    private static int compCount, swapCount;
 7 
    private static int compCount, swapCount;
7
8
8 
    private class Entry implements Comparable {
 9 
    private class Entry implements Comparable {
Line 46... Line 47...
46 
    public void printArray( Object[] array, PrintStream ps ) {
 47 
    public void printArray( Object[] array, PrintStream ps ) {
47 
        int i=0;
 48 
        int i=0;
48 
        for( i=0; i<array.length-1; i++ ) { System.out.print(array[i] + ", "); }
 49 
        for( i=0; i<array.length-1; i++ ) { System.out.print(array[i] + ", "); }
49 
        System.out.println(array[i]); //print the last element
 50 
        System.out.println(array[i]); //print the last element
50 
    }
 51 
    }
- 
 
 52
- 
 
 53 
    // howMany should be how many numbers you want to generate
- 
 
 54 
    // order: 0 = random
- 
 
 55 
    //        1 = ascending
- 
 
 56 
    //        2 = descending
- 
 
 57 
    public Entry[] generateNumbers( int howMany, int order ) {
- 
 
 58 
        Random generator = new Random();
- 
 
 59 
        Entry[] answer = new Entry[howMany];
- 
 
 60
- 
 
 61 
        if( order < 0 || order > 2 ) throw new IllegalArgumentException();
- 
 
 62
- 
 
 63 
        for( int i=0; i<howMany; i++ ) {
- 
 
 64 
            //I deemed random int's from 0 to 10239 to be a good test
- 
 
 65 
            if( order == 0 ) { answer[i] = new Entry(generator.nextInt(10240)); }
- 
 
 66 
            else if( order == 1) { answer[i] = new Entry(i); } //ascending
- 
 
 67 
            else { answer[i] = new Entry(howMany-i-1); } //descending
- 
 
 68 
        }
- 
 
 69
- 
 
 70 
        return answer;
- 
 
 71 
    }
- 
 
 72
- 
 
 73 
    private StringBuffer generateBlankSB() {
- 
 
 74 
        return new StringBuffer("                                ");
- 
 
 75 
    }
- 
 
 76
- 
 
 77 
    private String generateOutputLine( String name ) {
- 
 
 78 
        StringBuffer output = new StringBuffer(name); //put the name
- 
 
 79 
        StringBuffer spaces = new StringBuffer();
- 
 
 80 
 
- 
 
 81 
        for( int i=output.length(); i<20; i++ ) { spaces.append(" "); }
- 
 
 82 
        output.append(spaces);
- 
 
 83 
        output.append(getCompCount()); //appends the current number of comps
- 
 
 84 
 
- 
 
 85 
        spaces = new StringBuffer();
- 
 
 86 
        for( int i=output.length(); i<48; i++ ) { spaces.append(" "); }
- 
 
 87 
        output.append(spaces);
- 
 
 88 
        output.append(getSwapCount()); //appends the current number of swaps
- 
 
 89 
 
- 
 
 90 
        return output.toString();
- 
 
 91 
    }
51
92
- 
 
 93
52 
    public void testBubbleSort() {
 94 
    public void testBubbleSort( Entry[] array ) {
- 
 
 95 
        resetSwapCount();
- 
 
 96 
        resetCompCount();
- 
 
 97
- 
 
 98 
        SortMethods.BubbleSort(array);
- 
 
 99
- 
 
 100 
        System.out.println( generateOutputLine("BubbleSort"));
- 
 
 101 
    }
- 
 
 102 
 
- 
 
 103 
    public void testImprovedBubbleSort( Entry[] array ) {
- 
 
 104 
        resetSwapCount();
- 
 
 105 
        resetCompCount();
- 
 
 106
- 
 
 107 
        SortMethods.ImprovedBubbleSort(array);
- 
 
 108 
 
53 
        Entry[] array = { new Entry(3), new Entry(2), new Entry(1), new Entry(12), new Entry(812), new Entry(10), new Entry(4) };
 109 
        System.out.println( generateOutputLine("Impr. BubbleSort"));
- 
 
 110 
    }
- 
 
 111
- 
 
 112 
    public void testSelectionSort( Entry[] array ) {
- 
 
 113 
        resetSwapCount();
- 
 
 114 
        resetCompCount();
- 
 
 115
- 
 
 116 
        SortMethods.SelectionSort(array);
- 
 
 117 
 
- 
 
 118 
        System.out.println( generateOutputLine("SelectionSort"));
- 
 
 119 
    }
- 
 
 120
- 
 
 121 
    public void testInsertionSort( Entry[] array ) {
- 
 
 122 
        resetSwapCount();
- 
 
 123 
        resetCompCount();
- 
 
 124 
 
- 
 
 125 
        SortMethods.InsertionSort(array);
- 
 
 126 
 
- 
 
 127 
        System.out.println( generateOutputLine("InsertionSort"));
- 
 
 128 
    }
- 
 
 129
- 
 
 130 
    public void testShellSort( Entry[] array ) {
- 
 
 131 
        resetSwapCount();
- 
 
 132 
        resetCompCount();
- 
 
 133 
 
- 
 
 134 
        SortMethods.ShellSort(array);
- 
 
 135 
 
- 
 
 136 
        System.out.println( generateOutputLine("ShellSort"));
- 
 
 137 
    }
- 
 
 138 
 
- 
 
 139 
    public void testMergeSort( Entry[] array ) {
- 
 
 140 
        resetSwapCount();
- 
 
 141 
        resetCompCount();
- 
 
 142 
 
- 
 
 143 
        SortMethods.MergeSort(array);
54 
 
 144 
 
55 
        printArray(array,System.out);
 145 
        System.out.println( generateOutputLine("MergeSort"));
- 
 
 146 
    }
- 
 
 147 
 
56 
        SortMethods.QuickSort(array,0,array.length);
 148 
    public void testHeapSort( Entry[] array ) {
- 
 
 149 
        resetSwapCount();
- 
 
 150 
        resetCompCount();
- 
 
 151 
 
57 
        printArray(array,System.out);
 152 
        SortMethods.HeapSort(array);
58 
 
 153 
 
59 
        System.out.println("swapcount: " + getSwapCount());
 154 
        System.out.println( generateOutputLine("HeapSort"));
60 
        System.out.println("compcount: " + getCompCount());
 - 
 
61 
    }
 155 
    }
62 
 
 156 
 
- 
 
 157 
    public void testQuickSort( Entry[] array ) {
- 
 
 158 
        resetSwapCount();
- 
 
 159 
        resetCompCount();
- 
 
 160 
 
- 
 
 161 
        SortMethods.QuickSort(array);
- 
 
 162 
 
- 
 
 163 
        System.out.println( generateOutputLine("QuickSort"));
- 
 
 164 
    }
- 
 
 165
- 
 
 166 
    public void runTest() {
- 
 
 167
- 
 
 168 
        //make 6 arrays
- 
 
 169 
        Entry[] array = generateNumbers(512,0);
- 
 
 170 
        Entry[] arrayc1 = new Entry[array.length];
- 
 
 171 
        Entry[] arrayc2 = new Entry[array.length];
- 
 
 172 
        Entry[] arrayc3 = new Entry[array.length];
- 
 
 173 
        Entry[] arrayc4 = new Entry[array.length];
- 
 
 174 
        Entry[] arrayc5 = new Entry[array.length];
- 
 
 175 
        Entry[] arrayc6 = new Entry[array.length];
- 
 
 176
- 
 
 177 
        //fill the copies from the original
- 
 
 178 
        System.arraycopy(array,0,arrayc1,0,array.length);
- 
 
 179 
        System.arraycopy(array,0,arrayc2,0,array.length);
- 
 
 180 
        System.arraycopy(array,0,arrayc3,0,array.length);
- 
 
 181 
        System.arraycopy(array,0,arrayc4,0,array.length);
- 
 
 182 
        System.arraycopy(array,0,arrayc5,0,array.length);
- 
 
 183 
        System.arraycopy(array,0,arrayc6,0,array.length);
- 
 
 184
- 
 
 185 
        System.out.println("Test Case 1: Array Length 512 Composed of Random Elements");
- 
 
 186 
        StringBuffer header = generateBlankSB();
- 
 
 187 
        header.insert(0,"Method");
- 
 
 188 
        header.insert(20,"Number Compares");
- 
 
 189 
        header.insert(48,"Number Swaps");
- 
 
 190 
        System.out.println(header);
- 
 
 191 
 
- 
 
 192 
        testBubbleSort(array);
- 
 
 193 
        testImprovedBubbleSort(arrayc1);
- 
 
 194 
        testSelectionSort(arrayc2);
- 
 
 195 
        testInsertionSort(arrayc3);
- 
 
 196 
        testShellSort(arrayc4);
- 
 
 197 
        testMergeSort(arrayc5);
- 
 
 198 
        testQuickSort(arrayc6);
- 
 
 199 
    }
63 
}
 200 
}
64 
 
 201