Understanding Radix Sort Algorithm [duplicate]

Question

I am trying to understand how this radix sort algorithm works. I am new to algorithms and bits so this isn't coming easy to me. So far i have added these comments to my code to try and make it easier to understand. I am not sure if I have grasped the concept correctly so if anyone can see any problems with my comments/something I am not understanding correctly please help me out :)

Also would anyone be able to explain this line of code to me: mask = 1 << bit;

My commented code:

public static ArrayList<Integer> RadixSort(ArrayList<Integer> a)
    //This method implements the radix sort algorithm, taking an integer array as an input
    {
        ArrayList<Integer> array = CopyArray(a);
        //Created a new integer array called 'array' and set it to equal the array inputed to the method
        //This was done by copying the array entered to the method through the CopyArray method, then setting the results of the method to the new empty array

        Integer[] zerobucket = new Integer[a.size()];
        Integer[] onebucket = new Integer[a.size()];
        //Created two more integer arrays to act as buckets for the binary values
        //'zerobucket' will hold array elements where the ith bit is equal to 0
        //'onebucket' will hold array elements where the ith bit is equal to 1

        int i, bit;
        //Created two integer variables i & bit, these will be used within the for loops below
        //Both i & bit will be incremented to run the radix sort for every bit of the binary value, for every element in the array

        Integer element, mask;
        //Created an integer object called element, this will be used to retrieve the ith element of the unsorted array
        //Created an integer object called mask, this will be used to compare the bit values of each element

        for(bit=0; bit<8; ++bit)
        //Created a for loop to run for every bit of the binary value e.g.01000000
        //Change from 8 to 32 for whole integers - will run 4 times slower
        {
            int zcount = 0;
            int ocount = 0;
            //Created two integer variables to allow the 'zerobucket' and 'onebucket' arrays to be increment within the for loop below

            for(i=0; i<array.size(); ++i)
            //Created a nested for loop to run for every element of the unsorted array
            //This allows every bit for every binary value in the array
            {
                element = array.get(i);
                //Set the variable 'element' to equal the ith element in the array
                mask = 1 << bit;

                if ((element & mask) == 0)
                //If the selected bit of the binary value is equal to 0, run this code
                {
                    zerobucket[zcount++] = array.get(i);
                    //Set the next element of the 'zerobucket' array to equal the ith element of the unsorted array
                }
                else
                //Else if the selected but of the binary value is not equal to 0, run this code
                {
                    onebucket[ocount++] = array.get(i);
                    //Set the next element of the 'onebucket' array to equal the ith element of the unsorted array
                }
            }

            for(i=0; i<ocount; ++i)
            //Created a for loop to run for every element within the 'onebucket' array
            {
                array.set(i,onebucket[i]);
                //Appended the ith element of the 'onebucket' array to the ith position in the unsorted array
            }

            for(i=0; i<zcount; ++i)
            //Created a for loop to run for every element within the 'zerobucket' array
            {
                array.set(i+ocount,zerobucket[i]);
                //Appended the ith element of the 'zerobucket' array to the ith position in the unsorted array
            }
        }
        return(array);
        //Returned the sorted array to the method
    }

I did not write this code I was given it to try to understand

wait..didn't you ask this question before? stackoverflow.com/a/27745848/3808877 — Jobs
– Jobs, Commented Jan 2, 2015 at 21:18

Trevor Brown · Accepted Answer · 2015-01-02 19:10:20Z

I'll answer your questions in reverse order...

mask = 1 << bit;

Due to precedence rules, you could write this as

mask = (1 << bit);

Which is a bit more obvious. Take the integer 1 (0x01), shift it left by the bit position, and assign it to mask. So if bit is 2, mask is 00000010 (skipping leading zeroes). If bit is 4, mask is 00001000. And so on.

The reason for the mask is the line that follows:

if ((element & mask) == 0)

which is meant to identify whether the bit as the position bit is a 1 or zero. An item ANDed with the bitmask will either be zero or non-zero depending on whether the bit in the same position as the 1 in the bitmask is 0 or non-zero respectively.

Now the more complicated question. The algorithm in question is a least significant bit radix sort, meaning a radix sort in which the passes over the sorted values go from the least to most significant (or in the case of software integers, right to left) bits.

The following pseudocode describes your code above:

array = copy (a)
for every bit position from 0 to radix // radix is 8
    for each item in array
        if bit at bit position in item is 0
            put item in zeroes bucket
        else
            put item in ones bucket
    array = ordered concatenation of ones bucket and zeroes bucket
return array

So why does this work? You can think of this as an iterative weighted ranking of the items in the array. All other bits being equal, an item with a 1 bit will be a larger item than an item with a 0 bit (rank the items). Each pass becomes more important to final position (weight the rankings). The successive application of these binary sorts will result in items that more often have a 1 being more often placed in the 1's bucket. Each time that an item stays in the 1's bucket when other items don't, that item improves its relative position in the 1's bucket when compared to other items that in future passes may also have a 1. Consistent presence in the 1's bucket is then associated with consistent improvement in position, the logical extreme of which will be the largest value in the array.

Hope that helps.

Collectives™ on Stack Overflow

Understanding Radix Sort Algorithm [duplicate]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related