Algorithm Implementation/Sorting/Radix sort
Radix Sort
[edit | edit source]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
[edit | edit source]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
[edit | edit source]// 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
[edit | edit source]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
[edit | edit source]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)