Subversion Repositories programming

Rev

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

Rev 53 Rev 54
Line 82... Line 82...
82 
            for( int c = 0; c < d; c++ )
 82 
            for( int c = 0; c < d; c++ )
83 
                //applies Insertion sort to the skip sequence
 83 
                //applies Insertion sort to the skip sequence
84 
                SkipInsertionSort(a, c, d);
 84 
                SkipInsertionSort(a, c, d);
85 
    }
 85 
    }
86
86
- 
 
 87 
    public static void MergeSort( Comparable[] a ) {
- 
 
 88 
        //call mergesort on the whole array
- 
 
 89 
        MergeSortHelper(a,0,a.length);
- 
 
 90 
    }
- 
 
 91
87 
    // PRECONDITION: 0 <= p <= q <= a.length
 92 
    // PRECONDITION: 0 <= p <= q <= a.length
88 
    // POSTCONDITION: a[p..q-1] is in ascending order
 93 
    // POSTCONDITION: a[p..q-1] is in ascending order
89 
    public static void MergeSort( Comparable[] a, int p, int q ) {
 94 
    private static void MergeSortHelper( Comparable[] a, int p, int q ) {
90 
        if (q-p < 2) return;
 95 
        if (q-p < 2) return;
91 
        int m = (p+q)/2;
 96 
        int m = (p+q)/2;
92 
        MergeSort(a, p, m);
 97 
        MergeSortHelper(a, p, m);
93 
        MergeSort(a, m, q);
 98 
        MergeSortHelper(a, m, q);
94 
        merge(a, p, m, q);
 99 
        merge(a, p, m, q);
95 
    }
 100 
    }
96 
 
 101 
 
97 
    // PRECONDITIONS: a[p..m-1] and a[m..q-1] are in ascending order;
 102 
    // PRECONDITIONS: a[p..m-1] and a[m..q-1] are in ascending order;
98 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
 103 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
Line 132... Line 137...
132 
        }
 137 
        }
133
138
134 
        a[i] = ai;
 139 
        a[i] = ai;
135 
    }
 140 
    }
136
141
- 
 
 142 
    public static void QuickSort( Comparable[] a ) {
- 
 
 143 
        //call the real quicksort with the needed parameters
- 
 
 144 
        QuickSortHelper(a,0,a.length);
- 
 
 145 
    }
- 
 
 146 
 
137 
    // PRECONDITION: 0 <= p <= q <= a.length
 147 
    // PRECONDITION: 0 <= p <= q <= a.length
138 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
 148 
    // POSTCONDITION: a[p] <= a[p+1] <= ... <= a[q-1]
139 
    public static void QuickSort( Comparable[] a, int p, int q ) {
 149 
    private static void QuickSortHelper( Comparable[] a, int p, int q ) {
140 
        if (q-p < 2) return;
 150 
        if (q-p < 2) return;
141 
        int j = partition(a, p, q);
 151 
        int j = partition(a, p, q);
142 
        QuickSort(a, p, j);
 152 
        QuickSortHelper(a, p, j);
143 
        QuickSort(a, j+1, q);
 153 
        QuickSortHelper(a, j+1, q);
144 
    }
 154 
    }
145 
 
 155 
 
146 
    // RETURNS: index j of pivot element a[j];
 156 
    // RETURNS: index j of pivot element a[j];
147 
    // POSTCONDITION: a[i] <= a[j] <= a[k] for p <= i <= j <= k < q;
 157 
    // POSTCONDITION: a[i] <= a[j] <= a[k] for p <= i <= j <= k < q;
148 
    private static int partition( Comparable[] a, int p, int q ) {
 158 
    private static int partition( Comparable[] a, int p, int q ) {