0

I'm trying to implement a radix sort on a 32 bit signed integer key in Java. Hence I thought that a radix sort would work well.

I am however having issues with how to implement the sort, in terms of how to deal with the fact that negative numbers are going to end up in the wrong place if just implemented naively.

Any help with this would be appreciated.

Cjen1
  • 1,826
  • 3
  • 17
  • 47
  • 2
    Invert the sorting order for the top bit – harold Oct 03 '17 at 08:19
  • @harold and just sort the previous sections as normal? – Cjen1 Oct 03 '17 at 08:24
  • 1
    Yes, the only difference is in the top bit. Btw you can treat the whole top *byte* as signed, since the same thing applies there. – harold Oct 03 '17 at 08:33
  • @harold thanks that's exactly what I was looking for. If you want to put it as an answer I'll accept it since it is the correct answer – Cjen1 Oct 03 '17 at 08:47
  • 2
    You can toggle the sign bit (xor with 0x80) when indexing via the most significant byte, which is one way to invert the sorting order for the top bit as commented by harold. – rcgldr Oct 03 '17 at 09:20

1 Answers1

0

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.

Already treated in Radix Sort for Negative Integers

François LEPORCQ
  • 552
  • 2
  • 9