Radix Sort Working

Question

i wanted to know the logic of following radix sort program.

#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;
}

i am stuck because i dont quite understand the while(1) loop..

so far what i have come to know is :

INT_MIN=-2147483648

this is same as value of bit in rad_short_u()

i had debugged the program, due to rand() % 512-256, some -ve values are also generated,

during first pass it swaps all -ve values to one side(from starting) and +ve after that from next pass it shifts left to 1 bit so bit's value becomes 1073741824 from then to until it becomes 1 array remains same.

please help me to understand the program logic.

Answer 1

To understand this program, you need to understand both quicksort and most-significant-bit radix sort.

Like quicksort, it partitions the array into parts, then recursively sorts the parts. It first partitions based on the value of the most significant bit. Then it recurses on both halves. But this time, for each half, it partitions based on the second most significant bit. Then it divides again, and for each 1/4, it partitions on the 3rd most significant bit...

Note that while I am saying "1/2", "1/4", and so on, it will not typically divide the array into exactly 1/2, 1/4, etc. The size of each division will depend on the distribution of numbers in the array. For a normal quicksort, the size of each division would depend on the element chosen as "pivot", but that is not true for this "radix quicksort" -- the sequence of "pivots" is fixed.

Note, also, that unlike a normal quicksort, which can go quadratic and become very slow on certain inputs, this "quicksort" is guaranteed to finish in a fixed number of passes. Actually, the number of passes required is a constant, no matter the input. (This is a typical property of radix sorts -- performance tends to be insensitive to the input.)

Another interesting property: a normal quicksort would divide the array into 3 parts -- those lesser, equal, and greater than the pivot. But this "quicksort" always divides its input into exactly 2 parts on each pass -- those with a 0 bit in the position being tested, and those with a 1 bit.

I think the name of this algorithm is actually "binary quicksort".

Answer 2

Your while(1) loop operates bit-wise on unsigned integers. For each bit, it starts at the top and bottom of the list, finds the first pair of integers where the bit is set at the bottom and not the top, and swaps them. This corrects the ordering of these values at that bit.

It continues to do this until the top/bottom meet. In the end, each pass through the while(1) loop will result in the list having all numbers with that bit unset at the bottom of the list and all numbers with that bit set at the top of the list.

The list is then sorted, bitwise, starting at the MSB, then the second MSB, ..., and finally the LSB. The value INT_MIN is negative for signed integers, but corresponds to the MSB in twos-complement.

The x[i] ^= INT_MIN lines allow the radix sort to correctly handle negative numbers. Signed integers are stored in twos-complement. This effectively means that negative numbers have their MSB set.

If you naively apply a radix sort to signed integers, you end up with the positive numbers sorted to be at lower indices than the negative numbers.

The x[i] ^= INT_MIN flips the MSB, which fixes this problem. The second x[i] ^= INT_MIN flips the bit back.