Вопросы по реализации сортировки Radix в Java

Следующая сортировка Radix выполняет четыре прохода сортировки подсчетом (256 сегментов, 32-разрядные целые числа, начиная с младших значащих цифр), взятых из учебник по алгоритмам Седжвика.

public class LSD {
    private final static int BITS_PER_BYTE = 8;

    // LSD sort an array of integers, treating each int as 4 bytes
    // assumes integers are nonnegative
    // [ 2-3x faster than Arrays.sort() ]
    public static void sort(int[] a) {
    int BITS = 32;                 // each int is 32 bits 
    int W = BITS / BITS_PER_BYTE;  // each int is 4 bytes
    int R = 1 << BITS_PER_BYTE;    // each bytes is between 0 and 255
    int MASK = R - 1;              // 0xFF

    int N = a.length;
    int[] aux = new int[N];

    for (int d = 0; d < W; d++) {         

        // compute frequency counts
        int[] count = new int[R+1];
        for (int i = 0; i < N; i++) {           
            int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
            count[c + 1]++;
        }

        // compute cumulates
        for (int r = 0; r < R; r++)
            count[r+1] += count[r];

        // for most significant byte, 0x80-0xFF comes before 0x00-0x7F
        if (d == W-1) {
            int shift1 = count[R] - count[R/2];
            int shift2 = count[R/2];
            for (int r = 0; r < R/2; r++)
                count[r] += shift1;
            for (int r = R/2; r < R; r++)
                count[r] -= shift2;
        }

        // move data
        for (int i = 0; i < N; i++) {
            int c = (a[i] >> BITS_PER_BYTE*d) & MASK;
            aux[count[c]++] = a[i];
        }

        // copy back
        for (int i = 0; i < N; i++)
            a[i] = aux[i];
    }
}

Я понимаю большую часть кода, кроме этой части:

if (d == W-1) {
    int shift1 = count[R] - count[R/2];
    int shift2 = count[R/2];
    for (int r = 0; r < R/2; r++)
        count[r] += shift1;
    for (int r = R/2; r < R; r++)
        count[r] -= shift2;
}

Какова цель этого сегмента кода? Спасибо!


java sorting algorithm bit-manipulation radix-sort
person alwc    schedule 01.09.2014    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Блок кода делает именно то, что говорит комментарий:

для старшего байта 0x80-0xFF предшествует 0x00-0x7F

Причина этого такова: поскольку вы используете int, самым старшим битом является бит знак. Поэтому числа со старшим байтом в диапазоне 0x80-0xFF являются отрицательными числами, поэтому их следует размещать перед положительными числами, старший байт которых находится в диапазоне 0x00-0x7F.

Если вы спрашиваете, как блок кода достигает этого, вот краткая идея:

Поскольку вы поняли, как перемещаются данные, я предполагаю, что вы поняли, что делает count[] во всем коде. В кодовом блоке R — это верхняя граница, которая равна 0xFF + 1, а R / 2 — это 0x7F + 1. Следовательно, count[R] - count[R / 2] — это общее число в диапазоне от 0x80 до 0xFF. Таким образом, добавление сдвига от count[R] - count[R / 2] к count[0 .. R / 2] и вычитание его из count[R / 2 .. R] поможет числам в диапазоне от 0x00 до 0x7F иметь более высокое значение count, чем числа в диапазоне от 0x80 до 0xFF, в результате чего 0x80-0xFF предшествует 0x00-0x7F в конце концов.

Наконец, вам может быть любопытно: если первый бит является битом знака, почему 11111111 больше, чем 10000001? Разве это не -(127) < -(1)? Это связано с тем, что в компьютерной системе мы используем дополнение 2 вместо signed целые числа, поэтому 11111111 на самом деле означает -1, а 10000001 на самом деле означает -127.

person nevets    schedule 01.09.2014
comment
Спасибо, отличное объяснение! В этом случае этот сегмент кода действительно работает для int a[], который включает неотрицательные целые числа (в отличие от предположения автора кода в комментарии к строкам 4-5)? - person alwc; 01.09.2014