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 2,218 Posting Expert Featured Poster

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 0 Light Poster

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 2,218 Posting Expert Featured Poster

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 0 Light Poster

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?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.