Subversion Repositories programming

Rev

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

Rev 52 Rev 53
Line 4... Line 4...
4 
 
 4 
 
5 
class SortMethods {
 5 
class SortMethods {
6
6
7 
    // method to sort the array a (passed as a parameter)
 7 
    // method to sort the array a (passed as a parameter)
8 
    // this will sort in O(n^2) time
 8 
    // this will sort in O(n^2) time
9 
    public static Object[] BubbleSort( Object[] a ) {
 9 
    public static void BubbleSort( Comparable[] a ) {
10 
        //loop from the back of the array moving towards the beginning
 10 
        //loop from the back of the array moving towards the beginning
11 
        for( int i=a.length-1; i>0; i-- )
 11 
        for( int i=a.length-1; i>0; i-- )
12 
            //loop from the beginning of the array to position "i"
 12 
            //loop from the beginning of the array to position "i"
13 
            for( int j=0; j<i; j++ )
 13 
            for( int j=0; j<i; j++ )
14 
                //compare elements next to each other, and swap if necessary
 14 
                //compare elements next to each other, and swap if necessary
15 
                if( a[j] > a[j+1] ) arraySwap(a,j,j+1);
 15 
                if( a[j].compareTo( a[j+1] ) > 0 ) Test.swap(a,j,j+1);
16 
    }
 16 
    }
17
17
18 
    public static Object[] ImprovedBubbleSort( Object[] a ) {
 18 
    public static void ImprovedBubbleSort( Comparable[] a ) {
19 
        boolean inorder=true;
 19 
        boolean inorder=true;
20
20
21 
        for( int i=a.length-1; i>0; i-- ) {
 21 
        for( int i=a.length-1; i>0; i-- ) {
22 
            inorder=true;
 22 
            inorder=true;
23
23
24 
            for( int j=0; j<i; j++ )
 24 
            for( int j=0; j<i; j++ )
25 
                if( a[j] > a[j+1] ) {
 25 
                if( a[j].compareTo(a[j+1]) > 0 ) {
26 
                    arraySwap(a,j,j+1);
 26 
                    Test.swap(a,j,j+1);
27 
                    inorder=false;
 27 
                    inorder=false;
28 
                }
 28 
                }
29 
            if(inorder) break;  //array sorted, so bail out
 29 
            if(inorder) break;  //array sorted, so bail out
30 
        }
 30 
        }
31 
    }
 31 
    }
32
32
33 
    // method to sort the array a (passed as a paramter)
 33 
    // method to sort the array a (passed as a paramter)
34 
    // this will sort in O(n^2) time
 34 
    // this will sort in O(n^2) time
35 
    public static Object[] SelectionSort( Object[] a ) {
 35 
    public static void SelectionSort( Comparable[] a ) {
36 
        //loop from the back of the array moving towards the front
 36 
        //loop from the back of the array moving towards the front
37 
        for( int i=a.length-1; i>0; i-- ) {
 37 
        for( int i=a.length-1; i>0; i-- ) {
38 
            //placeholder for the maximum element
 38 
            //placeholder for the maximum element
39 
            int m=0;
 39 
            int m=0;
40 
            //find the maximum element in the array
 40 
            //find the maximum element in the array
41 
            for( int j=1; j<=i; j++ )
 41 
            for( int j=1; j<=i; j++ )
42 
                if( a[j] > a[m] ) m = j;
 42 
                if( a[j].compareTo(a[m]) > 0 ) m = j;
43
43
44 
            //swap the "i"th element with the maximum element
 44 
            //swap the "i"th element with the maximum element
45 
            arraySwap(a,i,m);
 45 
            Test.swap(a,i,m);
46 
        }
 46 
        }
47 
    }
 47 
    }
48
48
49 
    // method to sort the array a (passed as a parameter)
 49 
    // method to sort the array a (passed as a parameter)
50 
    // this will sort in O(n^2) time
 50 
    // this will sort in O(n^2) time
51 
    public static Object[] InsertionSort( Object[] a ) {
 51 
    public static void InsertionSort( Comparable[] a ) {
52 
        //iterate through the array from the beginning to the end
 52 
        //iterate through the array from the beginning to the end
53 
        for ( int i=1; i<a.length; i++ ) {
 53 
        for ( int i=1; i<a.length; i++ ) {
54 
            //store a[i] in a temp location
 54 
            //store a[i] in a temp location
55 
            Object ai = a[i];
 55 
            Comparable ai = a[i];
56 
            int j=i; //start for the inner loop
 56 
            int j=i; //start for the inner loop
57
57
58 
            //find the place to insert ai, and shift elements down
 58 
            //find the place to insert ai, and shift elements down
59 
            for ( j=i; j>0 && a[j-1]>ai; j-- )
 59 
            for ( j=i; j>0 && a[j-1].compareTo(ai) > 0; j-- )
60 
                a[j] = a[j-1]; //shift down
 60 
                a[j] = a[j-1]; //shift down
61
61
62 
            //insert ai into position a[j]
 62 
            //insert ai into position a[j]
63 
            a[j] = ai;
 63 
            a[j] = ai;
64 
        }
 64 
        }
65 
    }
 65 
    }
66
66
- 
 
 67 
    private static void SkipInsertionSort( Comparable[] a, int c, int d ) {
- 
 
 68 
        for( int i = c+d; i < a.length; i+=d ) {
- 
 
 69 
            Comparable ai = a[i];
- 
 
 70 
            int j = i;
- 
 
 71
- 
 
 72 
            while( j > c && a[j-d].compareTo(ai) > 0 ) {
- 
 
 73 
                a[j] = a[j-d];
- 
 
 74 
                j -= d;
67 
    //ShellSort
 75 
            }
- 
 
 76 
            a[j] = ai;
- 
 
 77 
        }
- 
 
 78 
    }
- 
 
 79
- 
 
 80 
    public static void ShellSort( Comparable[] a ) {
- 
 
 81 
        for( int d = a.length/2; d > 0; d /= 2 )
- 
 
 82 
            for( int c = 0; c < d; c++ )
- 
 
 83 
                //applies Insertion sort to the skip sequence
- 
 
 84 
                SkipInsertionSort(a, c, d);
- 
 
 85 
    }
- 
 
 86
- 
 
 87 
    // PRECONDITION: 0 <= p <= q <= a.length
- 
 
 88 
    // POSTCONDITION: a[p..q-1] is in ascending order
- 
 
 89 
    public static void MergeSort( Comparable[] a, int p, int q ) {
- 
 
 90 
        if (q-p < 2) return;
- 
 
 91 
        int m = (p+q)/2;
- 
 
 92 
        MergeSort(a, p, m);
68 
    //MergeSort
 93 
        MergeSort(a, m, q);
- 
 
 94 
        merge(a, p, m, q);
- 
 
 95 
    }
- 
 
 96 
 
- 
 
 97 
    // PRECONDITIONS: a[p..m-1] and a[m..q-1] are in ascending order;
- 
 
 98 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
- 
 
 99 
    private static void merge( Comparable[] a, int p, int m, int q ) {
- 
 
 100 
        if( a[m-1].compareTo(a[m]) <= 0 ) return;  // a[p..q-1] is already sorted
- 
 
 101 
        int i = p, j = m, k = 0;
- 
 
 102 
        Comparable[] aa = new Comparable[q-p];
- 
 
 103
- 
 
 104 
        while (i < m && j < q)
- 
 
 105 
            if( a[i].compareTo(a[j]) < 0 ) aa[k++] = a[i++];
- 
 
 106 
            else aa[k++] = a[j++];
- 
 
 107
- 
 
 108 
        if (i < m) System.arraycopy(a, i, a, p+k, m-i);  // shift a[i..m-1]
- 
 
 109 
        System.arraycopy(aa, 0, a, p, k);  // copy aa[0..k-1] to a[p..p+k-1];
- 
 
 110 
    }
- 
 
 111
- 
 
 112 
    // PRECONDITION: 0 <= p <= q <= a.length
- 
 
 113 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
- 
 
 114 
    public static void HeapSort( Comparable[] a ) {
- 
 
 115 
        for( int i = (a.length-1)/2; i >= 0; i-- )
- 
 
 116 
            heapify(a, i, a.length);
- 
 
 117
- 
 
 118 
        for( int j = a.length-1; j > 0; j-- ) {
- 
 
 119 
            Test.swap(a, 0, j);
- 
 
 120 
            heapify(a, 0, j);
- 
 
 121 
        }
- 
 
 122 
    }
- 
 
 123 
 
- 
 
 124 
    private static void heapify( Comparable[] a, int i, int n ) {
- 
 
 125 
        Comparable ai = a[i];
- 
 
 126 
        while( i < n/2 ) {                       // a[i] is not a leaf
- 
 
 127 
            int j = 2*i+1;                       // a[j] is ai¿s left child
- 
 
 128 
            if( j+1 < n && a[j+1].compareTo(a[j]) > 0 ) ++j;  // a[j] is ai¿s larger child
- 
 
 129 
            if( a[j].compareTo(ai) <= 0 ) break;              // a[j] is not out of order
- 
 
 130 
            a[i] = a[j];                         // promote a[j]
- 
 
 131 
            i = j;                               // move down to the next level
- 
 
 132 
        }
- 
 
 133
69 
    //HeapSort
 134 
        a[i] = ai;
- 
 
 135 
    }
- 
 
 136
- 
 
 137 
    // PRECONDITION: 0 <= p <= q <= a.length
- 
 
 138 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
- 
 
 139 
    public static void QuickSort( Comparable[] a, int p, int q ) {
- 
 
 140 
        if (q-p < 2) return;
- 
 
 141 
        int j = partition(a, p, q);
70 
    //QuickSort
 142 
        QuickSort(a, p, j);
- 
 
 143 
        QuickSort(a, j+1, q);
- 
 
 144 
    }
71 
 
 145 
 
- 
 
 146 
    // RETURNS: index j of pivot element a[j];
- 
 
 147 
    // POSTCONDITION: a[i] <= a[j] <= a[k] for p <= i <= j <= k < q;
- 
 
 148 
    private static int partition( Comparable[] a, int p, int q ) {
- 
 
 149 
        Comparable pivot = a[p];
- 
 
 150 
        int i = p, j = q;
- 
 
 151
- 
 
 152 
        while( i < j ) {
- 
 
 153 
            while( j > i && a[--j].compareTo(pivot) >= 0 )
- 
 
 154 
            ;  // empty loop
- 
 
 155
- 
 
 156 
            if( j > i ) { a[i] = a[j]; }
- 
 
 157
- 
 
 158 
            while( i < j && a[++i].compareTo(pivot) <= 0 )
- 
 
 159 
            ;  // empty loop
- 
 
 160
- 
 
 161 
            if( i < j ) { a[j] = a[i]; }
- 
 
 162 
        }
- 
 
 163
- 
 
 164 
        a[j] = pivot;
- 
 
 165 
        return j;
- 
 
 166 
    }
- 
 
 167
72 
    public static void arraySwap( Object[] a, int posA, int posB ) {
 168 
    public static void arraySwap( Object[] a, int posA, int posB ) {
73 
        Object temp = a[posB]; // temp = B
 169 
        Object temp = a[posB]; // temp = B
74 
        a[posB] = a[posA];     // B = A
 170 
        a[posB] = a[posA];     // B = A
75 
        a[posA] = temp;        // A = temp
 171 
        a[posA] = temp;        // A = temp
76 
    }
 172 
    }