<![CDATA[class RadixsortNode {
int[] arr;
RadixsortNode next = null;
RadixsortNode() {
}
RadixsortNode(int[] a) {
arr = new int[a.length];
for (int i = 0; i < a.length; i++)
arr[i] = a[i];
}
RadixsortNode(int n) {
arr = new int[n];
}
}
class Sorts {
void swap(Object[] a, int e1, int e2) {
Object tmp = a[e1]; a[e1] = a[e2]; a[e2] = tmp;
}
public void <a name="insertionsort">insertionsort</a>(BaseObject[] data) {
BaseObject tmp;
int i, j;
for (i = 1; i < data.length; i++) {
tmp = data[i];
for (j = i; j > 0 && tmp.isLessThan(data[j-1]); j--)
data[j] = data[j-1];
data[j] = tmp;
}
}
public void selectionsort(BaseObject[] data) {
int i,j,least;
for (i = 0; i < data.length-1; i++) {
for (j = i+1, least = i; j < data.length; j++)
if (data[j].isLessThan(data[least]))
least = j;
swap(data,least,i);
}
}
public void bubblesort(BaseObject[] data) {
int i,j;
for (i = 0; i < data.length-1; i++)
for (j = data.length-1; j > i; --j)
if (data[j].isLessThan(data[j-1]))
swap(data,j,j-1);
}
void Shellsort (BaseObject[] data) {
int i, j, k, h, hCnt, increments[] = new int[20];
BaseObject tmp;
// create an appropriate number of increments h
for (h = 1, i = 0; h < data.length; i++) {
increments[i] = h;
h = 3*h + 1;
}
// loop on the number of different increments h
for (i--; i >= 0; i--) {
h = increments[i];
// loop on the number of subarrays h-sorted in ith pass
for (hCnt = h; hCnt < 2*h; hCnt++) {
// insertion sort for subarray containing every hth element of array data
for (j = hCnt; j < data.length; ) {
tmp = data[j];
k = j;
while (k-h >= 0 && tmp.isLessThan(data[k-h])) {
data[k] = data[k-h];
k -= h;
}
data[k] = tmp;
j += h;
}
}
}
}
void moveDown(BaseObject[] data, int first, int last) {
int largest = 2*first + 1;
while (largest <= last) {
if (largest < last && // first has two children (at 2*first+1 and
data[largest].isLessThan(data[largest+1])) // 2*first+2)
largest++;
if (data[first].isLessThan(data[largest])) { // if necessary,
swap(data,first,largest); // swap values
first = largest; // and move down;
largest = 2*first + 1;
}
else largest = last + 1;// to exit the loop: the heap property
} // isn't violated by data[first]
}
void heapsort(BaseObject[] data) {
for (int i = data.length/2 - 1; i >= 0; --i)
moveDown(data,i,data.length-1);
for (int i = data.length-1; i >= 1; --i) {
swap(data,0,i);
moveDown(data,0,i-1);
}
}
void quicksort(BaseObject[] data, int first, int last) {
int lower = first + 1, upper = last;
swap(data,first,(first+last)/2);
BaseObject bound = data[first];
while (lower <= upper) {
while (data[lower].isLessThan(bound))
lower++;
while (bound.isLessThan(data[upper]))
upper--;
if (lower < upper)
swap(data,lower++,upper--);
else lower++;
}
swap(data,upper,first);
if (first < upper-1)
quicksort(data,first,upper-1);
if (upper+1 < last)
quicksort(data,upper+1,last);
}
void quicksort(BaseObject[] data) {
if (data.length < 2)
return;
int max = 0;
// find the largest element and put it at the end of data;
for (int i = 1; i < data.length; i++)
if (data[max].isLessThan(data[i]))
max = i;
swap(data,data.length-1,max); // largest el is now in its
quicksort(data,0,data.length-2); // final position;
}
public void insertionsort(BaseObject[] data, int first, int last) {
BaseObject tmp;
int i, j;
for (i = first; i <= last; i++) {
tmp = data[i];
for (j = i; j > 0 && tmp.isLessThan(data[j-1]); j--)
data[j] = data[j-1];
data[j] = tmp;
}
}
void quicksort2(BaseObject[] data, int first, int last) {
if (last - first < 30)
insertionsort(data,first,last);
else {
int lower = first + 1, upper = last;
swap(data,first,(first+last)/2);
BaseObject bound = data[first];
while (lower <= upper) {
while (data[lower].isLessThan(bound))
lower++;
while (bound.isLessThan(data[upper]))
upper--;
if (lower < upper)
swap(data,lower++,upper--);
else lower++;
}
swap(data,upper,first);
if (first < upper-1)
quicksort2(data,first,upper-1);
if (upper+1 < last)
quicksort2(data,upper+1,last);
}
}
void quicksort2(BaseObject[] data) {
if (data.length < 2)
return;
int max = 0;
// find the largest element and put it at the end of data;
for (int i = 1; i < data.length; i++)
if (data[max].isLessThan(data[i]))
max = i;
swap(data,data.length-1,max); // largest el is now in its
quicksort2(data,0,data.length-2); // final position;
}
BaseObject[] temp; // used by merge();
void merge(BaseObject[] data, int first, int last) {
int mid = (first + last) / 2;
int i1 = 0, i2 = first, i3 = mid + 1;
while (i2 <= mid && i3 <= last)
if (data[i2].isLessThan(data[i3]))
temp[i1++] = data[i2++];
else temp[i1++] = data[i3++];
while (i2 <= mid)
temp[i1++] = data[i2++];
while (i3 <= last)
temp[i1++] = data[i3++];
for (i1 = 0, i2 = first; i2 <= last; data[i2++] = temp[i1++]);
}
void mergesort(BaseObject[] data, int first, int last) {
if (first < last) {
int mid = (first + last) / 2;
mergesort(data, first, mid);
mergesort(data, mid+1, last);
merge(data, first, last);
}
}
void mergesort(BaseObject[] data) {
temp = new BaseObject[data.length];
mergesort(data,0,data.length-1);
}
final int radix = 10;
final int digits = 10;
final int bits = 31;
void radixsort(int[] data) {
int d, j, k, factor;
Queue[] queues = new Queue[radix]; // radix is 10;
for (d = 0; d < radix; d++)
queues[d] = new Queue();
for (d = 1, factor = 1; d <= digits; factor *= radix, d++) {
for (j = 0; j < data.length; j++)
queues[(data[j] / factor) % radix].enqueue(new Integer(data[j]));
for (j = k = 0; j < radix; j++)
while (!queues[j].isEmpty())
data[k++] = ((Integer) queues[j].dequeue()).intValue();
}
}
void bitRadixsort(int[] data) {
int d, j, k, factor, mask = 1;
Queue[] queues = new Queue[2];
queues[0] = new Queue();
queues[1] = new Queue();
for (d = 1; d <= bits; d++) {
for (j = 0; j < data.length; j++)
queues[(data[j] & mask) == 0 ? 0 : 1].enqueue(new Integer(data[j]));
mask <<= 1;
k = 0;
while (!queues[0].isEmpty())
data[k++] = ((Integer) queues[0].dequeue()).intValue();
while (!queues[1].isEmpty())
data[k++] = ((Integer) queues[1].dequeue()).intValue();
}
}
void clear(int[] arr, int q) {
arr[q] = -1;
}
boolean isEmpty(int q) {
return q == -1;
}
void radixsort2(int[] data) {
int d, j, k, factor, where;
int[] queues = new int[data.length], queueHeads = new int[radix];
int[] queueTails = new int[radix];
RadixsortNode n2 = new RadixsortNode(data), n1 = new RadixsortNode();
n1.arr = data;
n2.next = n1;
n1.next = n2;
for (j = 0; j < radix; j++)
clear(queueHeads,j);
for (d = 1, factor = 1; d <= digits; factor *= radix, d++) {
for (j = 0; j < data.length; j++) {
where = (n1.arr[j] / factor) % radix; // dth digit;
if (isEmpty(queueHeads[where]))
queueTails[where] = queueHeads[where] = j;
else {
queues[queueTails[where]] = j;
queueTails[where] = j;
}
}
for (j = 0; j < radix; j++)
if (!(isEmpty(queueHeads[j])))
clear(queues,queueTails[j]);
for (j = k = 0; j < radix; j++)
while (!(isEmpty(queueHeads[j]))) {
n2.arr[k++] = n1.arr[queueHeads[j]];
queueHeads[j] = queues[queueHeads[j]]; // also clears
} // queueHeads[];
n2 = n2.next;
n1 = n1.next;
}
if (digits % 2 != 0) // if digits is an odd number;
for (d = 0; d < data.length; d++)
data[d] = n1.arr[d];
}
void bitRadixsort2(int[] data) {
int d, j, k, factor, where, mask = 1;
int[] queues = new int[data.length], queueHeads = new int[radix];
int[] queueTails = new int[radix];
RadixsortNode n2 = new RadixsortNode(data), n1 = new RadixsortNode();
n1.arr = data;
n2.next = n1;
n1.next = n2;
clear(queueHeads,0);
clear(queueHeads,1);
for (d = 1; d <= bits; d++, mask <<= 1) {
for (j = 0; j < data.length; j++) {
where = (n1.arr[j] & mask) == 0 ? 0 : 1;
if (isEmpty(queueHeads[where]))
queueTails[where] = queueHeads[where] = j;
else {
queues[queueTails[where]] = j;
queueTails[where] = j;
}
}
for (j = 0; j < 2; j++)
if (!(isEmpty(queueHeads[j])))
clear(queues,queueTails[j]);
for (j = k = 0; j < 2; j++)
while (!(isEmpty(queueHeads[j]))) {
n2.arr[k++] = n1.arr[queueHeads[j]];
queueHeads[j] = queues[queueHeads[j]];
}
n2 = n2.next;
n1 = n1.next;
}
if (bits % 2 != 0) // if bits is an odd number;
for (d = 0; d < data.length; d++)
data[d] = n1.arr[d];
}
}
]]>