Subversion Repositories programming

Rev

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

Rev 51 Rev 53
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 
 
 4 
 
5 
public class Test {
 5 
public class Test {
6 
    private int compCount, swapCount;
 6 
    private static int compCount, swapCount;
7
7
8 
    private class Entry {
 8 
    private class Entry implements Comparable {
9 
        public int x;
 9 
        public int x;
10
10
11 
        public Entry( int x ) { this.x = x; }
 11 
        public Entry( int x ) { this.x = x; }
12
12
13 
        public boolean compareTo( Entry y ) {
 13 
        public int compareTo( Object o ) {
14 
            compCount++;
 14 
            compCount++;
15 
 
 - 
 
16 
            //this is the only way to do this in java
 15 
            if( !(o instanceof Entry) ) throw new IllegalArgumentException();
17 
            //java _requires_ a boolean in if() statements
 16
18 
            int temp = this.x - y.x;
 17 
            Entry y = (Entry)o;
19 
 
 - 
 
20 
            if( temp > 0 ) { return true; } // this > y
 - 
 
21 
            return false; // this <= y
 18 
            return this.x - y.x;
22 
        }
 19 
        }
23 
 
 20 
 
24 
        public Entry setEntry( int x ) {
 21 
        public Entry setEntry( int x ) {
25 
            return new Entry(x);
 22 
            return new Entry(x);
26 
        }
 23 
        }
27
24
28 
        //this is the only way a swap method can be made in java.
 - 
 
29 
        //the usual C++ (and others) way of using pointers is not
 - 
 
30 
        //possible in java. (I've come up with a very solid
 - 
 
31 
        //explanation of this. See me if you want to know.)
 - 
 
32 
        public void swap( Entry[] array, int posA, int posB ) {
 - 
 
33 
            Entry temp = array[posB];  // temp = B
 - 
 
34 
            array[posB] = array[posA]; // B = A
 - 
 
35 
            array[posA] = temp;        // A = temp
 - 
 
36 
            swapCount++;
 - 
 
37 
        }
 - 
 
38
- 
 
39 
        public String toString() { return Integer.toString(x); }
 25 
        public String toString() { return Integer.toString(x); }
40 
 
 26 
 
41 
    } //end Entry class
 27 
    } //end Entry class
42
28
43 
    public int getCompCount() { return compCount; }
 29 
    public int getCompCount() { return compCount; }
44 
    public int getSwapCount() { return swapCount; }
 30 
    public int getSwapCount() { return swapCount; }
45 
 
 31 
 
46 
    public void resetCompCount() { compCount = 0; }
 32 
    public void resetCompCount() { compCount = 0; }
47 
    public void resetSwapCount() { swapCount = 0; }
 33 
    public void resetSwapCount() { swapCount = 0; }
48 
 
 34 
 
- 
 
 35 
    //this is the only way a swap method can be made in java.
- 
 
 36 
    //the usual C++ (and others) way of using pointers is not
- 
 
 37 
    //possible in java. (I've come up with a very solid
- 
 
 38 
    //explanation of this. See me if you want to know.)
- 
 
 39 
    public static void swap( Object[] array, int posA, int posB ) {
- 
 
 40 
        Object temp = array[posB];  // temp = B
- 
 
 41 
        array[posB] = array[posA]; // B = A
- 
 
 42 
        array[posA] = temp;        // A = temp
- 
 
 43 
        swapCount++;
- 
 
 44 
    }
49 
 
 45 
 
- 
 
 46 
    public void printArray( Object[] array, PrintStream ps ) {
- 
 
 47 
        int i=0;
- 
 
 48 
        for( i=0; i<array.length-1; i++ ) { System.out.print(array[i] + ", "); }
- 
 
 49 
        System.out.println(array[i]); //print the last element
- 
 
 50 
    }
- 
 
 51
50 
    public void testBubbleSort() {
 52 
    public void testBubbleSort() {
51 
        Entry[] array = { new Entry(3), new Entry(2), new Entry(1) };
 53 
        Entry[] array = { new Entry(3), new Entry(2), new Entry(1), new Entry(12), new Entry(812), new Entry(10), new Entry(4) };
52 
 
 - 
 
53 
        for( int i=0; i<array.length; i++ ) { System.out.print(array[i] + ", "); }
 - 
 
54 
        System.out.println();
 - 
 
55 
 
 54 
 
- 
 
 55 
        printArray(array,System.out);
- 
 
 56 
        SortMethods.QuickSort(array,0,array.length);
56 
        array = BubbleSort(array);
 57 
        printArray(array,System.out);
57 
 
 58 
 
58 
        for( int i=0; i<array.length; i++ ) { System.out.print(array[i] + ", "); }
 59 
        System.out.println("swapcount: " + getSwapCount());
59 
        System.out.println();
 60 
        System.out.println("compcount: " + getCompCount());
60 
    }
 61 
    }
61
- 
 
62 
    public Entry[] BubbleSort( Entry[] a ) {
 - 
 
63 
        for( int i=a.length-1; i>0; i-- )
 - 
 
64 
            for( int j=0; j<i; j++ )
 - 
 
65 
                if( a[j].compareTo(a[j+1]) ) a[j].swap(a,j,j+1);
 - 
 
66 
 
 62 
 
67 
        return a;
 - 
 
68 
    }
 - 
 
69
- 
 
70 
}
 63 
}
71 
 
 64