awjackin35
asked on
Radix Sort
template <class Item>
Could someone tell me what the variable bytesword is? Can someone tell me what "static Item aux[maxN]" is used for? I want to implement this in my program but I can't use a template. In my class this line would be public:
"void radixLSD(Item a[], int l, int r)" but what would be my private variables? Would I declare Item[maxN] as int Item[maxN]? Are these just generic variables in the template?
template <class Item>
void radixLSD(Item a[], int l, int r)
{ static Item aux[maxN];
for (int d = bytesword-1; d >= 0; d--)
{
int i, j, count[R+1];
for (j = 0; j < R; j++) count[j] = 0;
for (i = l; i <= r; i++)
count[digit(a[i], d) + 1]++;
for (j = 1; j < R; j++)
count[j] += count[j-1];
for (i = l; i <= r; i++)
aux[count[digit(a[i], d)]++] = a[i];
for (i = l; i <= r; i++) a[i] = aux[i-l];
}
}
Could someone tell me what the variable bytesword is? Can someone tell me what "static Item aux[maxN]" is used for? I want to implement this in my program but I can't use a template. In my class this line would be public:
"void radixLSD(Item a[], int l, int r)" but what would be my private variables? Would I declare Item[maxN] as int Item[maxN]? Are these just generic variables in the template?
template <class Item>
void radixLSD(Item a[], int l, int r)
{ static Item aux[maxN];
for (int d = bytesword-1; d >= 0; d--)
{
int i, j, count[R+1];
for (j = 0; j < R; j++) count[j] = 0;
for (i = l; i <= r; i++)
count[digit(a[i], d) + 1]++;
for (j = 1; j < R; j++)
count[j] += count[j-1];
for (i = l; i <= r; i++)
aux[count[digit(a[i], d)]++] = a[i];
for (i = l; i <= r; i++) a[i] = aux[i-l];
}
}
>>Would I declare Item[maxN] as int Item[maxN]?
Just as I posted that, I noticed the parameter Item a[]. That is the thing to be sorted, so if you called the function as radixLSD<int>, that would have to be defined as an array of ints.
int sortThisPlease[50];
//fill the array here
radixLSD<int>(sortThisPlea
The code seems a bit strange though - I would suggest testing with a raw function that uses ints, rather than templating one. When that works, you can do the clever stuff :-)
Just as I posted that, I noticed the parameter Item a[]. That is the thing to be sorted, so if you called the function as radixLSD<int>, that would have to be defined as an array of ints.
int sortThisPlease[50];
//fill the array here
radixLSD<int>(sortThisPlea
The code seems a bit strange though - I would suggest testing with a raw function that uses ints, rather than templating one. When that works, you can do the clever stuff :-)
ASKER
This is from Algorithms in C++ by Sedgewick. I really can't understand the explanation in the book but he calls this a pure radix sort.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I *think* it's 8 (eight)
If you reverse the for loop in this example...
http://phoenix.liu.edu/~mdevi/algo/RadixSort.htm
If you reverse the for loop in this example...
http://phoenix.liu.edu/~mdevi/algo/RadixSort.htm
When you call this function, you'd do it like
radixLSD<int> (your parameters)
passing in the type of Item. The idea is that the code can be used for other data types, so in effect the line in question would become
static int aux[maxN]
you wouldn't have to declare it yourself - that's what this code is for.
Have a look at the place you got this code from - they should have documented it a bit.