c - Radix Sort Base 16 (Hexadecimals)

Question

I have spent more 10hr+ on trying to sort the following(hexadecimals) in LSD radix sort, but no avail. There is very little material on this subject on web.

0 4c7f cd80 41fc 782c 8b74 7eb1 9a03 aa01 73f1

I know I have to mask and perform bitwise operations to process each hex digit (4 bits), but have no idea on how and where.

I'm using the code (I understand) from GeeksforGeeks

void rsort(int a[], int n) {
    int max = getMax(a, n);
    for (int exp = 1; max / exp > 0; exp *= 10) {   
        ccsort(a, n, exp);
    }
}

int getMax(int a[], int n) {
    int max = a[0];
    int i = 0;
    for (i = 0; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

void ccsort(int a[], int n, int exp) {

    int count[n];
    int output[n];
    int i = 0;

    for (i = 0; i < n; i++) {
        count[i] = 0;
        output[i] = 0;
    }
    for (i = 0; i < n; i++) {
        ++count[(a[i] / exp) % 10];
    }
    for (i = 1; i <= n; i++) {
        count[i] += count[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        output[count[(a[i] / exp) % 10] - 1] = a[i];
        --count[(a[i] / exp) % 10];
    }
    for (i = 0; i < n; i++) {
        a[i] = output[i];
    }
}

I have also checked all of StackOverFlow on this matter, but none of them covers the details.

Answer 1

Your implementation of radix sort is slightly incorrect:

• it cannot handle negative numbers
• the array count[] in function ccsort() should have a size of 10 instead of n. If n is smaller than 10, the function does not work.
• the loop for cumulating counts goes one step too far: for (i = 1; i <= n; i++). Once again the <= operator causes a bug.
• you say you sort by hex digits but the code uses decimal digits.

Here is a (slightly) improved version with explanations:

void ccsort(int a[], int n, int exp) {

    int count[10] = { 0 };
    int output[n];
    int i, last;

    for (i = 0; i < n; i++) {
        // compute the number of entries with any given digit at level exp
        ++count[(a[i] / exp) % 10];
    }
    for (i = last = 0; i < 10; i++) {
        // update the counts to have the index of the place to dispatch the next
        // number with a given digit at level exp
        last += count[i];
        count[i] = last - count[i];
    }
    for (i = 0; i < n; i++) {
        // dispatch entries at the right index for its digit at level exp
        output[count[(a[i] / exp) % 10]++] = a[i];
    }
    for (i = 0; i < n; i++) {
        // copy entries batch to original array
        a[i] = output[i];
    }
}

int getMax(int a[], int n) {
    // find the largest number in the array
    int max = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

void rsort(int a[], int n) {
    int max = getMax(a, n);
    // for all digits required to express the maximum value
    for (int exp = 1; max / exp > 0; exp *= 10) {   
        // sort the array on one digit at a time
        ccsort(a, n, exp);
    }
}

The above version is quite inefficient because of all the divisions and modulo operations. Performing on hex digits can be done with shifts and masks:

void ccsort16(int a[], int n, int shift) {

    int count[16] = { 0 };
    int output[n];
    int i, last;

    for (i = 0; i < n; i++) {
        ++count[(a[i] >> shift) & 15];
    }
    for (i = last = 0; i < 16; i++) {
        last += count[i];
        count[i] = last - count[i];
    }
    for (i = 0; i < n; i++) {
        output[count[(a[i] >> shift) & 15]++] = a[i];
    }
    for (i = 0; i < n; i++) {
        a[i] = output[i];
    }
}

void rsort16(int a[], int n) {
    int max = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    for (int shift = 0; (max >> shift) > 0; shift += 4) {   
        ccsort16(a, n, shift);
    }
}

It would be approximately twice as fast to sort one byte at a time with a count array of 256 entries. It would also be faster to compute the counts for all digits in one pass, as shown in rcgldr's answer.

Note that this implementation still cannot handle negative numbers.