Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Radix Sort

Posted on 2001-09-10
5
Medium Priority
?
313 Views
Last Modified: 2008-02-01
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];
      }
  }
0
Comment
Question by:awjackin35
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
5 Comments
 
LVL 4

Expert Comment

by:IainHere
ID: 6474047
First off, this is not a template class, it is a template function.  So no public/private etc.  bytesword is not defined anywhere in this snippet, so I can't answer that question - neither is R.  

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.
0
 
LVL 4

Expert Comment

by:IainHere
ID: 6474071
>>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>(sortThisPlease, 50, 50);

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 :-)
0
 

Author Comment

by:awjackin35
ID: 6474404
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.
0
 
LVL 4

Accepted Solution

by:
IainHere earned 160 total points
ID: 6474435
The example in isn't templeted though, is it?  Try using the original version.  Do you understand both the logic of the approach and the way that his code goes about using it.  Explanations of radix sorting abound:

http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page518.html#45625

Get the raw version from
http://www.ime.usp.br/~yoshi/mac324/Sedgewick/chap10.txt
0
 
LVL 6

Expert Comment

by:Triskelion
ID: 6484126
I *think* it's 8 (eight)
If you reverse the for loop in this example...
http://phoenix.liu.edu/~mdevi/algo/RadixSort.htm
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question