Odd radix sort problem

[wallace]

For the radix sort, use a straightforward iterative approach, using at most 2 1D arrays (not linked lists)

This is part of a project I'm supposed to code. I don't even understand how this is supposed to work. I use radix sorts all the time, but I almost always use Linked Lists, and if I don't I use 2, 10, or 16 buckets for EACH iteration, how can I do an entire radix sort in only one extra linear array? Could someone help me out with some psydo-code here?

[na_th_an]

I think it's just a matter of simulating linked lists within a 1D array (hate that way to call them, they are actually called vectors). I.e. when you add a value you have to shift right the ones that are supposed to be after and when you take a value away you have to shift them left.

[Moneo]

Does this project insist that you use a radix sort, or is your task to provide a good, working sort?
*****

[wallace]

It must be a radix sort, I'm still having trouble seeing it. Could someone please post some pseudocode?

[Moneo]

It must be a radix sort, I'm still having trouble seeing it. Could someone please post some pseudocode?

I did a Google search on "radix.sort" and found some interesting sites, like NIST. You might want to look at some of these for the pseudo-code that you're looking for.

Much to my surprise, a radix sort emulates the way we used to sort punched cards using a card sorting machine (sorter) back in the 1960's. What a radix sort calls "buckets" were called "pockets" on a sorter.

I have played around with similar sorts over the years. What complicates matters is whether you intend to sort strings or values, and if the strings contain only numbers or can be alphanumeric. Same problem applied on the sorter by the way.

Also, if the strings are only numbers, what is the maximum number of digits that any of these strings can have? This determines the number of passes over all the data.

I thing you need more detailed specs for the radix sort you need to write. Otherwise, if you attempt to write the sort to handle every case and data size, you're program will turn into a monster.
*****

[wallace]

My problem is not figuring out how a radix sort works, I use radix sort all the time. The problem is that I'm not allowed to use buckets.

[Moneo]

That's like being given a canoe, and not allowed to use paddles. :wink:
*****

[na_th_an]

As mentioned, you can emulate them with static structures such as arrays.