static void shellsort(int[] A) {
for (int i=A.length/2; i>2; i/=2) { // For each increment
for (int j=0; j<i; j++) { // Sort each sublist
inssort2(A, j, i);
}
}
inssort2(A, 0, 1); // Could call regular inssort here
}
/** Modified Insertion Sort for varying increments */
static void inssort2(int[] A, int start, int incr) {
for (int i=start+incr; i<A.length; i+=incr)
for (int j=i; (j>=incr) && (A[j] < A[j-incr]); j-=incr)
Swap.swap(A, j, j-incr);
}
.
static void quicksort(Comparable[] A, int i, int j) { // Quicksort
int pivotindex = findpivot(A, i, j); // Pick a pivot
Swap.swap(A, pivotindex, j); // Stick pivot at end
// k will be the first position in the right subarray
int k = partition(A, i, j-1, A[j]);
Swap.swap(A, k, j); // Put pivot in place
if ((k-i) > 1) { quicksort(A, i, k-1); } // Sort left partition
if ((j-k) > 1) { quicksort(A, k+1, j); } // Sort right partition
}
static int findpivot(Comparable[] A, int i, int j)
{ return (i+j)/2; }
.
.
for (i=0; i<A.length; i++)
B[A[i]] = A[i];
.
static void radix(Integer[] A, int k, int r) {
Integer[] B = new Integer[A.length];
int[] count = new int[r]; // Count[i] stores number of records with digit value i
int i, j, rtok;
for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits
for (j=0; j<r; j++) { count[j] = 0; } // Initialize count
// Count the number of records for each bin on this pass
for (j=0; j<A.length; j++) { count[(A[j]/rtok)%r]++; }
// count[j] will be index in B for last slot of bin j.
// First, reduce count[0] because indexing starts at 0, not 1
count[0] = count[0] - 1;
for (j=1; j<r; j++) { count[j] = count[j-1] + count[j]; }
// Put records into bins, working from bottom of bin
// Since bins fill from bottom, j counts downwards
for (j=A.length-1; j>=0; j--) {
B[count[(A[j]/rtok)%r]] = A[j];
count[(A[j]/rtok)%r] = count[(A[j]/rtok)%r] - 1;
}
for (j=0; j<A.length; j++) { A[j] = B[j]; } // Copy B back
}
}
.