Radix Sort for Negative Integers

问题:

I am trying to implement radix sort for integers, including negative integers. For non-negative ints, I was planning to create a queue of 10 queues correspondingly for the digits 0-9 and implement the LSD algorithm. But I was kind of confused with negative integers. What I am thinking now, is to go ahead and create another queue of 10 queues for them and separately sort them and then at the end, I will gave 2 lists, one containing negative ints sorted and the other containing non-negative ints. And finally I would merge them.

What do you think about this? Is there more efficient way to handle with negative integers?

Thank you!

回答1:

You can treat the sign as a special kind of digit. You sort the pile on the units, then the tens, etc. and finally on the sign. This does produce a reversed order for the negatives, you then simply reverse the contents of that bucket. It's how old mechanical card sorters worked.

回答2:

Note that the sign bit is the uppermost bit in a signed integer, but all numbers are treated by radix sort as unsigned integers by default. So you need to tell the algorithm that negative numbers are smaller than positive ones. In case of 32-bit signed integers, you can sort three lower bytes first, then sort the fourth (upper) byte with the sign bit inverted so that 0 will be used for negative numbers instead of 1, and consequently they will go first.

I strongly advise to sort numbers byte-by-byte rather than by decimal digits, because it's far easier for the machine to pick up bytes than extract digits.

回答3:

One more solution is to separate negative integers from the array, make them positive, sort as positive values using radix, then reverse it and append with sorted non-negative array.

回答4:

Absolutely! Of course you do have to take care of splitting up the negatives from the positives but luckily this is easy. At the beginning of your sorting algorithm all you have to do is partition your array around the value 0. After that, radix sort below and above the partition.

Here is the algorithm in practice. I derived this from Kevin Wayne and Bob Sedgewick's 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:

Probably the easiest way to handle signed values is to offset the starting position for the accumulation (i.e., generation of positional offsets) when operating on the most significant digit. Transforming the input so all digits may be treated as unsigned is also an option, but requires applying an operation over the value array at least twice (once to prepare input and again to restore output).

This uses the first technique as well as byte-sized digits (byte access is generally more efficient):

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

Note: Code is untested. Apologies for any errors/typos.

回答6:

Your radix sort wont be faster than the famous comparison sorts if you dont use "bitshift" and "bitwise AND" for radix calculation.

Computers use 2's complement to represent signed numbers, here the sign-bit lies at the leftmost end of a binary digit, in memory representation

eg
436163157 (as 32 bit number) = 00011001 11111111 01010010 01010101
-436163157 (as 32 bit number) = 11100110 00000000 10101101 10101011

1 (as 32 bit number) = 00000000 00000000 00000000 00000001
-1 (as 32 bit number) = 11111111 1111111 1111111 11111111

0 is represented as = 00000000 00000000 00000000 00000000
Highest negative value as = 10000000 00000000 00000000 00000000

So you see, the more negative a number becomes, it looses that many 1's, a small negative number has many 1's, if you set only the sign-bit to 0, it becomes a very large positive number. Vice versa a small positive number becomes a large negative number.

In radix sort the key to sorting negative numbers is how you handle the last 8 bits, for negative numbers at least the last bit has to be 1, in 32-bit scheme it has to be from
10000000 00000000 00000000 00000000 which is the most negative value farthest from zero to 11111111 11111111 11111111 11111111 which is -1. If you look at the leftmost 8 bits, the magnitude ranges from 10000000 to 11111111, i.e. from 128 to 255.

These values can be obtained by this code piece

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

For negative numbers V will always lie from 128 upto 255. For positive numbers it will be from 0 to 127. As said earlier, the value of M will be 255 for -1 and 128 for highest negative number in 32-bit scheme. Build up your histogram as usual. Then from index 128 to 255 do the cumulative sum, then add frequency of 255 to 0, and proceed the cumulative sum from 0 till index 127. Perform the Sort as usual. This technique is both optimal, fast, elegant and neat both in theory and in practice. No need of any kind of separate lists nor order reversal after sorting nor converting all inputs to positive which make the sort slow and messy.

For the code see Radix Sort Optimization
A 64-bit version can be built using same concepts

Further read:
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html

回答7:

This can be done without requiring partitioning or having to practically invert the MSB. Here's a working solution in Java:

public class RadixSortsInterviewQuestions {
    private static final int MSB = 64;

    static Map.Entry<Integer, Integer> twoSum(long[] a, long sum) {
        int n = a.length - 1;
        sort(a, MSB, 0, n);

        for (int i = 0, j = n; i < j; ) {
            long t = a[i] + a[j];
            if (t == sum) {
                return new SimpleImmutableEntry<>(i, j);
            } else if (t < sum) {
                i++;
            } else {
                j--;
            }
        }
        return null;
    }

    // Binary MSD radix sort: https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations
    private static void sort(long[] a, int d, int lo, int hi) {
        if (hi < lo || d < 1) return;

        int left = lo - 1;
        int right = hi + 1;

        for (int i = left + 1; i < right; ) {
            if (isBitSet(a[i], d)) {
                swap(a, i, --right);
            } else {
                left++;
                i++;
            }
        }
        sort(a, d - 1, lo, left);
        sort(a, d - 1, right, hi);
    }

    private static boolean isBitSet(long x, int k) {
        boolean set = (x & 1L << (k - 1)) != 0;

        // invert signed bit so that all positive integers come after negative ones
        return (k == MSB) != set;
    }

    private static void swap(long[] a, int i, int j) {
        long tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

回答8:

The accepted answer requires one more pass than necessary.

Just flip the sign bit.

This is essentially the answer posted by punpcklbw, but there is a tiny caveat that needs to be addressed. Specifically, this assumes you are working with a two's-complement representation, which is true for 99.999% of us. For example, both Java and Rust specify that signed integers use two's-complement. The C and C++ specs don't require any specific format, but neither MSVC, GCC, nor LLVM support other representations. In assembly, almost any CPU you will deal with is two's-complement, and you will surely already know otherwise.

The following table demonstrates that simply flipping the sign bit will cause two's-complement integers to sort correctly when sorted lexicographically. The first column gives a binary value, the second column gives the interpretation of those bits as 4-bit signed integers, and the third column gives the interpretation of those bits with the high bit flipped.

Binary    | 2s-comp  | Flip sign
----------+----------+----------
0000      | 00       | -8
0001      | +1       | -7
0010      | +2       | -6
0011      | +3       | -5
0100      | +4       | -4
0101      | +5       | -3
0110      | +6       | -2
0111      | +7       | -1
1000      | -8       | 00
1001      | -7       | +1
1010      | -6       | +2
1011      | -5       | +3
1100      | -4       | +4
1101      | -3       | +5
1110      | -2       | +6
1111      | -1       | +7

The answer given by punpcklbw recommends only flipping the bit when you're looking at the highest byte, but my gut tells me that it would be faster to simply flip the top bit every time before you pull out the byte you're looking at. That's because doing a single xor every time to flip the bit will be faster than doing a branch every time to decide if you should flip or not.

[An important detail to mention, which some textbooks fail to address properly, is that a real implementation should sort by byte, not by decimal digit. This is obviously still correct, because you're just sorting by a radix of 256 instead of 10, but thinking about it this way will lead to better implementations.]