Algorithm Implementation/Sorting/Radix sort

Radix Sort

Radix Sort is a sorting algorithm designed to work on items where the key of each item is an ordered set of integers in the range 0 to (N-1) inclusive both ends, or can be transformed into such an ordered set.

C# least significant digit (LSD) radix sort implementation

Here we sort an unsigned integer array that's passed to the RadixSort method (Note: all arrays in C#/.NET are reference types, and therefore a is a reference to an array).

Source: article on www.osix.net (here)

public void RadixSort(uint[] a)
{  
    // our helper array 
    uint[] t=new uint[a.Length]; 
     
    // number of bits our group will be long 
    int r=4; // try to set this also to 2, 8 or 16 to see if it is quicker or not 
     
    // number of bits of a C# int 
    int b=32; 
     
    // counting and prefix arrays
    // (note dimensions 2^r which is the number of all possible values of a r-bit number) 
    int[] count=new int[1<<r]; 
    int[] pref=new int[1<<r]; 
     
    // number of groups 
    int groups=(int)Math.Ceiling(b/(double)r); 
     
    // the mask to identify groups 
    int mask = (1<<r)-1; 
     
    // the algorithm: 
    for (int c=0, shift=0; c<groups; c++, shift+=r)
    { 
        // reset count array 
        for (int j=0; j<count.Length; j++)
            count[j]=0;

        // counting elements of the c-th group 
        for (int i=0; i<a.Length; i++)
            count[(a[i]>>shift)&mask]++;

        // calculating prefixes 
        pref[0]=0; 
        for (int i=1; i<count.Length; i++)
            pref[i]=pref[i-1]+count[i-1];

        // from a[] to t[] elements ordered by c-th group 
        for (int i=0; i<a.Length; i++)
            t[pref[(a[i]>>shift)&mask]++]=a[i];

        // a[]=t[] and start again until the last group 
        t.CopyTo(a,0); 
    } 
    // a is sorted 
}

C++ LSD radix sort example of non-recursive implementation

// C++ LSD Radix Sort example, queue implementation

#include <iostream.h>
#include <cstdlib.h>
#include <ctime.h>

using std::cout; // Remove this line for older C++ compilers

typedef struct slist_ { 
    int val;
    struct slist_ *next; 
} slist;

slist *radixsort(slist *L, int t) 
{
    int i, j, d, m=1;
    slist *temp, *head[10], *tail[10];

    // Process t digits
    for (j=1; j<=t; j++) 
    { 
        // Initialize the queues, 0 to 9
        for (i=0; i<=9; i++)
        {
            head[i] = NULL;
            tail[i] = NULL;
        }

        // Process the list L
        while ( L != NULL ) 
        {
            // Get the decimal digit with place value m
            d = static_cast<int>(L->val/m)%10;
            
            // Make temp point to the current list item
            temp = L;

            // Make L point to the next list item
            L = L->next;

            // Disconnect the current list item, making it self-contained
            temp->next = NULL;

            if (head[d]!= NULL)
            {   // The queue for digit d is not empty

                // Add the list item to the end of the queue for digit d
                tail[d]->next = temp;

                // Make tail[d] point to the new tail item of queue d
                tail[d] = temp;
            }
            else
            {   // The queue for digit d is empty
                head[d] = temp;  // Point to the new head
                tail[d] = temp;  // Point to the new tail
            }
        } // while

        // Find the index, d, of the first non-empty queue
        d=0;
        while (head[d]==NULL)
            d++;

        // Point to the first item of the first non-empty queue
        L = head[d];

        // Point to the last item of the first non-empty queue
        temp = tail[d];

        // Append the items of the remaining non-empty queues
        // to the tail of list L.
        d++;
        while (d<10)
        {
            if (head[d]!=NULL)
            {
                // Append the items of non-empty queue d to list L
                temp->next = head[d];

                // Point to the new tail of list L
                temp = tail[d];
            }

            d++;
        } // while

        // Prepare to process the next more significant digit
        m = m*10;
    } // for

    return L;
}

int main()
{
    // Initialize the random number seed with the time
    srand( static_cast<unsigned int>(time(NULL)) );

    const int size = 20;
    int n[size];
    int i, max=-1, t=0;

    // Generate some random numbers
    slist *start=NULL,*end=NULL,*temp;
    for (i=0; i<size; i++)
    {
        n[i] = rand();
    }

    // Find the largest value and create a linked list of the random values
    for (i=0; i<size; i++)
    {
        // Find the largest value
        if (n[i] > max)
            max = n[i];

        // Create a new node
        temp = new slist;

        // Fill the node with a random value
        temp->val = n[i];

        // Seal the node
        temp->next = NULL;

        if (start != NULL)
        {   // Append the new node to the linked list
            end->next = temp;
            end = temp;
        }
        else
        {   // Add the first node to the linked list
            start = temp;
            end = temp;
        }
    }

    // Find the number of decimal digits in the largest random value
    while (max>0)
    {
        t=t+1;
        max=max/10;    
    }

    // Perform the radix sort
    start = radixsort(start, t);

    // Display the results
    cout << "after radix sort.\n";
    temp = start;
    for (i=0; i<size; i++)
    {
        cout << temp->val << "\n";
        temp = temp->next;
    }

    // Return a zero to the calling script, batch file, or command shell
    // to indicate successful completion.
    return 0;
} // main

Phix

function radixSortn(sequence s, integer n)
sequence buckets = repeat({},10)
sequence res = {}
    for i=1 to length(s) do
        integer digit = remainder(floor(s[i]/power(10,n-1)),10)+1
        buckets[digit] = append(buckets[digit],s[i])
    end for
    for i=1 to length(buckets) do
        integer len = length(buckets[i])
        if len!=0 then
            if len=1 or n=1 then
                res &= buckets[i]
            else
                res &= radixSortn(buckets[i],n-1)
            end if
        end if
    end for
    return res
end function
 
function split_by_sign(sequence s)
sequence buckets = {{},{}}
    for i=1 to length(s) do
        integer si = s[i]
        if si<0 then
            buckets[1] = append(buckets[1],-si)
        else
            buckets[2] = append(buckets[2],si)
        end if
    end for
    return buckets
end function
 
function radixSort(sequence s)
integer mins = min(s)
integer passes = max(max(s),abs(mins))
    passes = floor(log10(passes))+1
    if mins<0 then
        sequence buckets = split_by_sign(s)
        buckets[1] = reverse(sq_uminus(radixSortn(buckets[1],passes)))
        buckets[2] = radixSortn(buckets[2],passes)
        s = buckets[1]&buckets[2]
    else
        s = radixSortn(s,passes)
    end if
    return s
end function

Python LSD radix sort

def radixSort(a,n,maxLen):
    for x in range(maxLen):
        bins = [[] for i in range(n)]
        for y in a:
            bins[(y/n**x)%n].append(y)
        a=[]
        for section in bins:
            a.extend(section)
    return a

if __name__ == "__main__":
    import random
    import timeit
    a = [random.randint(0,10000) for i in xrange(1000000)]
    t = timeit.Timer('radixSort(a, 10, 5)', 'from __main__ import radixSort, a')
    print t.timeit(number=1)