questions on radix sort programs

[demroth]

I have been reading the posts on radix sort here at DaniWeb and at http://www.cubic.org/docs/radix.htm. I have already created the code for the counting sort which will do the rest but I do not understand how to do the radix part. I guess what I am asking is if you have a 3 digit number like 315. How would you break it up by the ones, tens, and then hundreds?

[VernonDozier]

I have been reading the posts on radix sort here at DaniWeb and at http://www.cubic.org/docs/radix.htm. I have already created the code for the counting sort which will do the rest but I do not understand how to do the radix part. I guess what I am asking is if you have a 3 digit number like 315. How would you break it up by the ones, tens, and then hundreds?

Use the modulus operator (%) and the divide operator (/)

315 / 100 = 3
(315 % 100) / 10 = 1
315 % 10 = 5

You'll have to think of an efficient algorithm, but it will probably use a combination of / and %.

[demroth]

I am just brainstorming to design this function but any input would be helpful. If I tried something like the following...

for(i=0; i < arraysize; i++)
{
  //numbers are the integers from a file or array 
  numbers[i] % 10 >> ones[i];
  (numbers[i] % 100) / 10 >> tens[i];
   numbers[i] /100 >> hundreds[i];
 
  void sortingfunction(); //call to counting sort function to sort each

}

I would need to find a way to tell the counting sort function to sort by each ones, tens, and hundreds but I would need the function to keep the original number. Is there a function in a library that will sort or check by position?

[VernonDozier]

Not sure what you are trying to do. Before you isolate digits from a number, you need the number in some type of variable. If the number is in a string, that is an array of characters. Each character is a different digit. Neither the modulus or the division operator would be required to isolate the digits.

If the number is an integer, then isolate the digits using the / and % operators. how the data gets from the file to the string or integer is another topic, separate from extracting individual digits.

I don't know if you are using this (>>) as the operator used to get input from a stream or if you are using it as a bit-shift operator. It looks like numbers is an integer, not a stream, so you are trying to do a bit-shift? Not sure why. Use the assignment operator (=):

ones[i] = numbers[i] % 10;

That seems like the easiest way to do it to me.

[demroth]

Not sure what you are trying to do. Before you isolate digits from a number, you need the number in some type of variable. If the number is in a string, that is an array of characters. Each character is a different digit. Neither the modulus or the division operator would be required to isolate the digits.

If the number is an integer, then isolate the digits using the / and % operators. how the data gets from the file to the string or integer is another topic, separate from extracting individual digits.

Each digit is an integer. They are read from a file and stored in an array called numbers[]. I thought I was isolating each digit by using the / and % or did I get that wrong?

I don't know if you are using this (>>) as the operator used to get input from a stream or if you are using it as a bit-shift operator. It looks like numbers is an integer, not a stream, so you are trying to do a bit-shift? Not sure why. Use the assignment operator (=):

ones[i] = numbers[i] % 10;

That seems like the easiest way to do it to me.

Ok, what you suggest is what I was thinking of, but I used the wrong operator. Even with this the problem is how to get my counting sort function to sort by each digit. This is the counting sort function...

void countingSort(int numbers[], int size_of_array)
{
 // search for the minimum and maximum values in the input
 int i; 
 int min = numbers[0];
 int max = min;
 int counter;
 for(i = 0; i < size_of_array; ++i)
 {
  if (numbers[i] < min)
      min = numbers[i];
    else if (numbers[i] > max)
        max = numbers[i];
 }
 
 // create a counting array, counts, with a member for 
 // each possible discrete value in the input.  
 // initialize all counts to 0.
 int c = max - min + 1;
 
 int* counts = new int[c];
 
 for(i=0; i<c; ++i)
     counts[i] = 0;
 
 // accumulate the counts - the result is that counts will hold
 // the offset into the sorted array for the value associated with that index
 for(i=0; i < size_of_array; ++i)
     ++counts[numbers[i] - min];
 
 // store the elements in the array
 int j=0;
 int z;
 for(i=min; i<=max; i++)
 for(z = 0; z<counts[i-min]; z++)
 {
   numbers[j++] = i;
   counter = counter + 1;
 }
 cout<<"The cost of the function (counter) is " <<counter<<endl;
  delete[] counts;
 
}

I believe I could pass the ones, tens, and hundreds, as arguements but what else would I have to change to get the sort to work?