Radix Sort для отрицательных целых чисел

Ответ 1

Вы можете рассматривать знак как особый вид цифры. Вы сортируете кучу на единицах, потом десятки и т.д. И, наконец, на знаке. Это создает обратный порядок для негативов, тогда вы просто меняете содержимое этого ведра. Это как старые механические карточные сортировщики работали.

Ответ 2

Обратите внимание, что бит знака является самым верхним битом в целочисленном знаке, но по умолчанию все числа обрабатываются по методу radix как целые числа без знака. Поэтому вам нужно сказать алгоритму, что отрицательные числа меньше положительных. В случае 32-разрядных целых чисел со знаком сначала вы можете отсортировать три нижних байта, затем отсортировать четвертый (верхний) байт с инвертированным битом знака, так что 0 будет использоваться для отрицательных чисел вместо 1, и, следовательно, они будут первыми.

Я настоятельно рекомендую сортировать числа побайтовыми, а не десятичными цифрами, потому что машиной намного легче брать байты, чем извлекать цифры.

Ответ 3

Еще одно решение состоит в том, чтобы отделить отрицательные целые числа от массива, сделать их положительными, отсортировать как положительные значения с помощью radix, а затем отменить его и добавить с отсортированным неотрицательным массивом.

Ответ 4

Абсолютно! Конечно, вам нужно позаботиться о том, чтобы разделить негативы с положительными, но, к счастью, это легко. В начале вашего алгоритма сортировки все, что вам нужно сделать, - это разделить массив на значение 0. После этого, радикс сортирует ниже и выше раздела.

Вот алгоритм на практике. Я получил это от Kevin Wayne и Bob Sedgewick MSD radix sort: http://algs4.cs.princeton.edu/51radix/MSD.java.html

private static final int CUTOFF = 15;
private static final int BITS_PER_INT = 32;
private static final int BITS_PER_BYTE = 8;
private static final int R = 256;

public void sort(int[] a){
    int firstPositiveIndex = partition(0, a, 0, a.length-1);
    int[] aux =new int[a.length];
    if(firstPositiveIndex>0){
        recSort(a, firstPositiveIndex, a.length-1, 0,aux);
        recSort(a, 0, firstPositiveIndex-1, 0,aux);
    }else{//all positive
        recSort(a, 0, a.length-1, 0, aux);
    }
}

private void recSort(int[] a, int lo, int hi, int d, int[] aux){
    if(d>4)return;
    if(hi-lo<CUTOFF){
        insertionSort(a,lo, hi);
        return;
    }

    int[] count = new int[R+1];

    //compute counts
    int bitsToShift = BITS_PER_INT-BITS_PER_BYTE*d-BITS_PER_BYTE;
    int mask = 0b1111_1111;
    for(int i = lo; i<=hi; i++){
        int c = (a[i]>>bitsToShift) & mask;
        count[c+1]++;
    }

    //compute indices
    for(int i = 0; i<R; i++){
        count[i+1]=count[i]+count[i+1];
    }

    //distribute
    for(int i = lo; i<=hi; i++){
        int c = (a[i]>>bitsToShift) & mask;
        aux[count[c]+lo] = a[i];
        count[c]++;
    }
    //copy back
    for(int i = lo; i<=hi; i++){
        a[i]=aux[i];
    }

    if(count[0]>0)
        recSort(a, lo, lo+count[0]-1, d+1, aux);
    for(int i = 1; i<R; i++){
        if(count[i]>0)
            recSort(a, lo+count[i-1], lo+count[i]-1, d+1, aux);
    }
}

// insertion sort a[lo..hi], starting at dth character
private void insertionSort(int[] a, int lo, int hi) {
    for (int i = lo; i <= hi; i++)
        for (int j = i; j > lo && a[j] < a[j-1]; j--)
            swap(a, j, j-1);
}


//returns the index of the partition or to the right of where it should be if the pivot is not in the array 
public int partition(int pivot, int[] a, int lo, int hi){
    int curLo = lo;
    int curHi = hi;
    while(curLo<curHi){
        while(a[curLo]<pivot){
            if((curLo+1)>hi)return hi+1;
            curLo++;
        }

        while(a[curHi]>pivot){
            if((curHi-1)<lo)return lo-1;
            curHi--;
        }
        if(curLo<curHi){
            swap(a, curLo, curHi);
            if(a[curLo]!=pivot)curLo++;
            if(a[curHi]!=pivot)curHi--;             
        }
    }
    return curLo;
}


private void swap(int[] a, int i1, int i2){
    int t = a[i1];
    a[i1]=a[i2];
    a[i2]=t;
}

Ответ 5

Вероятно, самый простой способ обработки подписанных значений заключается в смещении начальной позиции для накопления (т.е. создания позиционных смещений) при работе с самой значительной цифрой. Преобразование ввода, поэтому все цифры могут рассматриваться как unsigned, также является опцией, но требует применения операции над массивом значений не менее двух раз (один раз для подготовки ввода и снова для восстановления вывода).

В этом случае используется первый метод, а также цифры в байтах (доступ к байтам обычно более эффективен):

void lsdradixsort(int* a, size_t n)
{
    // isolate integer byte by index.
    auto bmask = [](int x, size_t i)
    {
        return (static_cast<unsigned int>(x) >> i*8) & 0xFF;
    };

    // allocate temporary buffer.
    auto m = std::make_unique<int[]>(n);
    int* b = m.get();

    // for each byte in integer (assuming 4-byte int).
    for ( size_t i, j = 0; j < 4; j++ ) {
        // initialize counter to zero;
        size_t h[256] = {}, start;

        // histogram.
        // count each occurrence of indexed-byte value.
        for ( i = 0; i < n; i++ )
            h[bmask(a[i], j)]++;

        // accumulate.
        // generate positional offsets. adjust starting point
        // if most significant digit.
        start = (j != 3) ? 0 : 128;
        for ( i = 1+start; i < 256+start; i++ )
            h[i % 256] += h[(i-1) % 256];

        // distribute.
        // stable reordering of elements. backward to avoid shifting
        // the counter array.
        for ( i = n; i > 0; i-- )
            b[--h[bmask(a[i-1], j)]] = a[i-1];
        std::swap(a, b);
    }
}

Примечание: Код не проверен. Извинения за ошибки/опечатки.

Ответ 6

Ваша сортировка радиуса не будет быстрее, чем известные сортировки сравнения, если вы не используете "битдвиг" и "побитовое И" для вычисления радиуса.

Компьютеры используют 2 дополнения для представления числа со знаком, здесь знаковый бит лежит в самом левом конце двоичной цифры, в представлении памяти

например
 436163157 (как 32-разрядное число) = 0 0011001 11111111 01010010 01010101
-436163157 (как 32-разрядное число) = 1 1100110 00000000 10101101 10101011

1 (как 32-разрядное число) = 0 0000000 00000000 00000000 00000001
-1 (как 32-разрядное число) = 1 1111111 1111111 1111111 11111111

0 представляется как = 0 0000000 00000000 00000000 00000000
Наибольшее отрицательное значение как = 1 0000000 00000000 00000000 00000000

Таким образом, вы видите, что чем больше отрицательного числа становится, тем меньше, чем много 1, небольшое отрицательное число имеет много 1, если вы устанавливаете только знаковый бит в 0, он становится очень большим положительным числом. Наоборот, небольшое положительное число становится большим отрицательным числом.

В сортировке radix ключ для сортировки отрицательных чисел - это то, как вы обрабатываете последние 8 бит, для отрицательных чисел, по крайней мере, последний бит должен быть 1, в 32-битной схеме это должно быть от
1 0000000 00000000 00000000 00000000, что является самым отрицательным значением, наиболее удаленным от нуля до 1 1111111 11111111 11111111 11111111, которое равно -1. Если вы посмотрите на самые левые 8 бит, величина находится в диапазоне от 10000000 до 11111111, то есть от 128 до 255.

Эти значения могут быть получены с помощью этой кодовой части

V = ( A[i] >> 24 ) & 255

Для отрицательных чисел V всегда будет находиться от 128 до 255. Для положительных чисел оно будет от 0 до 127. Как было сказано ранее, значение M будет 255 для -1 и 128 для максимального отрицательного числа в 32-битном схема. Создайте свою гистограмму, как обычно. Затем из индекса 128 в 255 суммируйте сумму, затем добавьте частоту от 255 до 0 и выполните кумулятивную сумму от 0 до индекса 127. Выполните сортировку, как обычно. Этот метод является оптимальным, быстрым, элегантным и опрятным как в теории, так и на практике. Нет необходимости в каких-либо отдельных списках или изменении порядка после сортировки и преобразования всех входов в положительные, которые делают сортировку медленной и беспорядочной.

Для кода см. Оптимизация сортировки Radix
64-разрядную версию можно создать с использованием тех же концепций

Далее читайте:
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html