I have to figure out four sorting algorithms: Bubble, insertion, merge, and radix sorting. I've figured out the first three, but radix is giving me a lot of problems.

Basically, it's to compare running times with each sort. But just figuring out the algorithm for radix is giving me a problem. I know you can do it with queues, but we haven't learned that yet. So, I'm doing it with arrays, which is a lot harder.

If you don't know what radix sorting is, say you have a list of 6 numbers:
536
391
889
613
119
307
535

What radix sorting with do, is look at the first number first, then sort accordingly. So it'll look at the 5,3,8,6,1,3,5 and put them in order. So after the first run, it'll look like this:

119
391
307
536
535
613
889

Now that still isn't in order. So the second run through, it'll take all the numbers with 1, look at THEIR second number, and sort accordingly. After that is done, it'll look like this:

119
307
391
536
535
613
889

Still out of order, since the 500 numbers are messed up. Radix sort still needs to look at the third digit, then plan accordingly.

So the final result will end in a sorted list.

tldr; radix sorting is basically like putting things in alphabetical order.

Now I tried out some code that will work. My algorithm will start at the last number first then work its way towards to first number, using two arrays.

Here's my code so far. It compiles and runs without any errors;

int radixsort( long int array[], long int n){
int k=-9, i, j, m;
float power;
for(power=0;power<8;power++)
{
i=0;j=0;
while(k<=9)
{i=0;
while(i<n)
{
if((array/((int)pow(10,power))%10)==k){
sorted[j]=array[i];
j++; i++;}
else{
i++;}
}
k++;
}
}
for(m=0;m<n;m++){array[m]=sorted[m];}
}


Now I've gotten close. My results aren't just 0's anymore, they're sorted according to the last digit. So it has all the negatives with 9 at the end, negative numbers that have 8 at the end, etc. That was supposed to be the first step in my algorithm, then it would look at the next least significant number, and so on. I just don't know why the power loop isn't working. I appreciate any help you guys can give

[i] Hyper edit: I actually found out what was wrong and I got it to work. I'm going to leave this up until A) A mod decides to close it because the problem is solved or B) someone else can see what's wrong.




This message was edited by HyperShadow0213 on Nov 08 2009.

For further help with algorithms and general programming try xoax.net.

I don't have time to look in depth at the moment, but i'd say you're lucky that the 300's numbers aren't out of order as well. Radix sort in a nutshell goes through each digit column and sorts the numbers by that digit, you can sort by the digits going from the left to the right, or vis versa, it doesn't matter, but the thing about radix sort is it must preserve the ordering of the output when two inputs have the digit you are looking at equal to one another.

ex.

123
122

when sorting these two numbers going from the right to the left, the first step of radix sort would do this

122
123

then at the next step you'll see that it compares the middle digits, 2=2, so it should leave the numbers in the same order, however yours is not doing this so things like this can happen at the next step

123
122

which is not what you want.

radix sort is usually done like...

radix sort(array A)

for each digit column of each element in array A
do use a stable sorting algorithm

end radix sort

the key is using what is called a STABLE sorting algorithm...stable just means that it preserves the order of the input/output on ties. Since you've done merge sort, i believe that in most merge sort implementations that it is stable. Bascailly what you want to do is for each digit column, call merge sort to sort the numbers by that digit (you might have to change merge sort slightly accordingly) but this is the general idea behind radix sort.