static void
radixExchangeSort(int array[]) {
// Perumute the given array to be in ascending order.
res(array, 0, array.length, 31);
}
private static void
res(int array[], int left, int right, int bitNumber) {
// Permute the array segment array[left..right - 1] such that if
// left <= i < j < right, then array[i] < array[j] when the array elements
// are interpreted as bitNumber-bit values.
if ((left < right) && (bit > -1)) {
final int mid = bitPartition(array, left, right, bitNumber);
res(array, left, mid, bitNumber - 1);
res(array, mid, right, bitNumber - 1);
}
}
private static int
bitPartition(int array[], int left, int right, int bitNumber) {
// Permute the array segment array[left..right - 1] so that every element
// with bit bitNumber cleared appears before any element with bit bitNumber
// set. Return the smallest index of an element with bit bitNumber set.
final int bit = 1 << bitNumber;
// array[left'..left - 1] has bit bitNumber cleared.
// array[right..right' - 1] has bit bitNumber set.
while (left < right)
if ((array[left] & bit) != bit)
left++;
else if ((array[right - 1] & bit) == bit)
right--;
else {
final int temp = array[left];
array[left++] = array[--right];
array[right] = temp;
}
return left;
}
This page last modified on 24 January 2006.