Reverse Engineer Sorting Algorithm

Question

I have been given 3 algorithms to reverse engineer and explain how they work, so far I have worked out that I have been given a quick sorting algorithm and a bubble sorting algorithm; however i'm not sure what algorithm this is. I understand how the quick sort and bubble sort work, but I just can't get my head around this algorithm. I'm unsure what the variables are and was hoping someone out there would be able to tell me whats going on here:

public static ArrayList<Integer> SortB(ArrayList<Integer> a)
{
    ArrayList<Integer> array = CopyArray(a);
    Integer[] zero = new Integer[a.size()];
    Integer[] one = new Integer[a.size()];
    int i,b;
    Integer x,p;
    //Change from 8 to 32 for whole integers - will run 4 times slower
    for(b=0;b<8;++b)
    {
        int zc = 0;
        int oc = 0;
        for(i=0;i<array.size();++i)
        {
            x = array.get(i);
            p = 1 << b;
            if ((x & p) == 0)
            {
                zero[zc++] = array.get(i);
            }
            else
            {
                one[oc++] = array.get(i);
            }
        }
        for(i=0;i<oc;++i) array.set(i,one[i]);
        for(i=0;i<zc;++i) array.set(i+oc,zero[i]);
    }
    return(array);
}

Sergey Kalinichenko · Accepted Answer · 2015-01-02 02:59:48Z

4

This is a Radix Sort, limited to the least significant eight bits. It does not complete the sort unless you change the loop to go 32 times instead of 8.

Each iteration processes a single bit b. It prepares a mask called p by shifting 1 left b times. This produces a power of two - 1, 2, 4, 8, ..., or 1, 10, 100, 1000, 10000, ... in binary.

For each bit, the number of elements in the original array with bit b set to 1 and to 0 are separated into two buckets called one and zero. Once the separation is over, the elements are placed back into the original array, and the algorithm proceeds to the next iteration.

This implementation uses two times more storage than the size of the original array, and goes through the array a total of 16 times (64 times in the full version - once for reading and once for writing of data for each bit). The asymptotic complexity of the algorithm is linear.

answered Jan 2, 2015 at 2:59

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user3386109 Over a year ago

The asymptotic complexity of a radix sort is debatable. In fact, the first section of the wikipedia article that you cited is titled "Efficiency" and has a good summary of the debate.

Sergey Kalinichenko Over a year ago

@user3386109 Well, the "debate" over radix sort centers around an argument that the number of bits we must process should be considered a function of N (namely, at least LogN) based on an implicit assumption that all keys could be distinct. I am not sure if it's a solid assumption, though, especially if we sort lots of small numbers.

user3386109 Over a year ago

"based on an implicit assumption that all keys could be distinct" is more generally worded as "based on the assumption that the size of the array after removing duplicate keys is O(N)". You are correct that the radix sort is linear for the special case where the number of unique keys in the array is much less than N, i.e. the majority of the array consists of repeated keys.

Dima Over a year ago

@user3386109, the debate is rather academical: if you are sorting integers (or longs) in any real life computer program, the number of bits is a constant. In a way, it is a "function" of the data type, and not the size of the array.

StilesCrisis · Accepted Answer · 2015-01-02 02:54:31Z

1

Looks like a bit-by-bit radix sort to me, but it seems to be sorting backwards.

answered Jan 2, 2015 at 2:54

StilesCrisis

16.4k4 gold badges44 silver badges64 bronze badges

2 Comments

Prakash Kuma Over a year ago

But why the outer loop is being executed only 8 times.

StilesCrisis Over a year ago

It is only sorting the lower 8 bits for speed--as the comment says, doing all 32 bits is 4 times slower.

Collectives™ on Stack Overflow

Reverse Engineer Sorting Algorithm

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related