Поразрядная сортировка работает

я хотел знать логику следующей программы сортировки по основанию.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

typedef unsigned uint;
#define swap(a, b) { tmp = a; a = b; b = tmp; }
#define each(i, x) for (i = 0; i < x; i++)

/* sort unsigned ints */
static void rad_sort_u(uint *from, uint *to, uint bit)
{
    if (!bit || to < from + 1) return;

uint *ll = from, *rr = to - 1, tmp;
while (1) {
    /* find left most with bit, and right most without bit, swap */
    while (ll < rr && !(*ll & bit)) ll++;
    while (ll < rr &&  (*rr & bit)) rr--;
    if (ll >= rr) break;
    swap(*ll, *rr);
}

if (!(bit & *ll) && ll < to) ll++;
bit >>= 1;

rad_sort_u(from, ll, bit);
rad_sort_u(ll, to, bit);
}

/* sort signed ints: flip highest bit, sort as unsigned, flip back */
static void radix_sort(int *a, const size_t len)
{
size_t i;
uint *x = (uint*) a;

each(i, len) x[i] ^= INT_MIN;
rad_sort_u(x, x + len, INT_MIN);
each(i, len) x[i] ^= INT_MIN;
}

static inline void radix_sort_unsigned(uint *a, const size_t len)
{
rad_sort_u(a, a + len, (uint)INT_MIN);
}

int main(void)
{
int len = 16, x[16], i;
size_t len = 16, i;
each(i, len) x[i] = rand() % 512 - 256;

radix_sort(x, len);

each(i, len) printf("%d%c", x[i], i + 1 < len ? ' ' : '\n');

return 0;
}

я застрял, потому что я не совсем понимаю цикл while (1) ..

пока что я узнал:

INT_MIN=-2147483648

это то же самое, что и значение bit в rad_short_u()

я отладил программу, из-за rand() % 512-256 также генерируются некоторые значения -ve,

во время первого прохода он меняет все значения -ve в одну сторону (от начала), а +ve после этого со следующего прохода он сдвигается влево на 1 бит, поэтому значение бита становится 1073741824 с тех пор, пока оно не станет 1, массив остается прежним.

помогите пожалуйста понять логику программы.


c radix-sort
person MKS    schedule 28.06.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Чтобы понять эту программу, вам нужно понимать как быструю сортировку, так и сортировку по основанию по наибольшему разряду.

Как и быстрая сортировка, он разбивает массив на части, а затем рекурсивно сортирует части. Сначала он разделяется на основе значения старшего бита. Затем он повторяется на обеих половинах. Но на этот раз для каждой половины он разбивается на основе второго старшего бита. Затем он снова делится, и для каждой 1/4 он разделяется на 3-й старший бит...

Обратите внимание, что хотя я говорю «1/2», «1/4» и т. д., обычно массив не делится ровно на 1/2, 1/4 и т. д. Размер каждого деления будет зависеть от распределение чисел в массиве. Для обычной быстрой сортировки размер каждого деления будет зависеть от элемента, выбранного в качестве «осевого», но это не так для этой «быстрой сортировки по основанию» — последовательность «осевых» фиксирована.

Также обратите внимание, что в отличие от обычной быстрой сортировки, которая может стать квадратичной и стать очень медленной при определенных входных данных, эта «быстрая сортировка» гарантированно завершится за фиксированное количество проходов. На самом деле количество требуемых проходов является постоянным, независимо от входных данных. (Это типичное свойство поразрядных сортировок — производительность обычно нечувствительна к входным данным.)

Еще одно интересное свойство: обычная быстрая сортировка разделила бы массив на 3 части — меньшую, равную и большую, чем опорная. Но эта «быстрая сортировка» всегда делит входные данные ровно на 2 части на каждом проходе — те, у которых 0 бит в проверяемой позиции, и те, у которых 1 бит.

Я думаю, что название этого алгоритма на самом деле «бинарная быстрая сортировка».

person Alex D    schedule 28.06.2012

arrow_upward
0
arrow_downward

Ваш цикл while(1) работает побитно с целыми числами без знака. Для каждого бита он начинает с верхней и нижней части списка, находит первую пару целых чисел, где бит установлен внизу, а не вверху, и меняет их местами. Это корректирует порядок этих значений в этом бите.

Это продолжается до тех пор, пока верх/низ не встретятся. В конце концов, каждый проход через цикл while(1) приведет к тому, что в списке будут все числа с этим неустановленным битом в нижней части списка, а все числа с этим установленным битом в верхней части списка.

Затем список сортируется по битам, начиная с MSB, затем со второго MSB, ... и, наконец, с LSB. Значение INT_MIN отрицательно для целых чисел со знаком, но соответствует старшему биту в дополнении до двух.

Строки x[i] ^= INT_MIN позволяют сортировке по основанию правильно обрабатывать отрицательные числа. Целые числа со знаком хранятся в дополнении до двух. Фактически это означает, что отрицательные числа имеют установленный старший разряд.

Если вы наивно примените сортировку по основанию к целым числам со знаком, вы получите положительные числа, отсортированные по более низким индексам, чем отрицательные числа.

x[i] ^= INT_MIN переворачивает MSB, что устраняет эту проблему. Второй x[i] ^= INT_MIN переворачивает бит обратно.

person sfstewman    schedule 28.06.2012
comment
спасибо, теперь я понял алгоритм, кроме того, я также нашел его в книге Роберта Седжвика, где он дан как сортировка по системе счисления. - person MKS; 29.06.2012