Implement sort similar to radix

Question

hi i need to write sucj kind of sorting maybe it is similary to radix sort and also (this is not homework because i created it problem myself and please if anobody can help me) problem is like this suppose i have array int x[]=new int[]{4,5,3,2,1}; let write it into binary form 5 -0101 4- 0100 3-0011 2-0010 1-0001 i want to sort this elements by using bitwise operatos or check each bit and if less exchange it can anybody help me for example take 5 and 4 check first rightmost bit 0==0 so continue in the 1 index also 1==1 next the same 0=0 and last one 1>0 it means that first element is greater then second so exchange it

Paraphasing:

I need to create a sort similar to radix.

Suppose I have an array: int x[] = new int[] {4, 5, 3, 2, 1};

Or, in binary form: 5-0101 4-0100 3-0011 2-0010 1-0001

I want to sort these elements by using bitwise operators or check each bit and (if less) exchange it. For example, consider 5 and 4:

The leftmost or most significant bit (MSB) of 5 in binary is 0, as is the MSB of 4. Since 0 == 0 the process continues. The next two bits (0 then 1) are also equivalent. Finally the rightmost or least significant bit (LSB) of 5 is 1 whereas the LSB of 4 is 0, indicating that the two values should be exchanged.

@Greg S: Thanks, sometimes I can't help but try to decipher questions that I might otherwise be interested in; and I think it helps the community! — JYelton

polygenelubricants polygenelubricants · Accepted Answer · 2010-05-19T09:54:24

To get the k-th bit of an int x, you can do the following:

int bit = (x >> k) & 1;

Here's a test harness:

    int xs[] = {4,5,3,2,1};
    for (int k = 0; k < 4; k++) {
        for (int x : xs) {
            int bit = (x >> k) & 1;
            System.out.format("|%s|  ", bit);
        }
        System.out.println();
    }

This prints (with annotation)

x= 4    5    3    2    1  k=
  |0|  |1|  |1|  |0|  |1|  0
  |0|  |0|  |1|  |1|  |0|  1
  |1|  |1|  |0|  |0|  |0|  2
  |0|  |0|  |0|  |0|  |0|  3

The tricky bit here is the sign bit, i.e. bit 31 on an int. When it's 1, it signifies a negative number. You may want to first have an implementation that only works for positive int, and then add support for negative number later.

Implement sort similar to radix

1 Answers

See also