Cheap and Secure Web Hosting Provider : See Now

Which pass do you look at for Radix Sort stability?

, , No Comments
Problem Detail: 

I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title.

So in Radix Sort, you go digit by digit from least significant to most significant, and along the way you are swapping elements around. When considering the case where two digits are the same, do you look at the original array to decide which should come first, or do you look at the previous iteration?

In one case you would have to store the original to look back on, so my guess is it's not that, but I can't tell which provides the correct result by my own examples. Let me know if I need to describe my question better and I will try.

Asked By : Robert Whitmer
Answered By : D.W.

Radix sort always uses the results of the previous pass, not the original array. It does not attempt to store the original value of the array. You can find a description of radix sort at Wikipedia or in standard algorithms textbooks, and you'll see that it has this property.

As Wikipedia describes, radix sort is stable if you sort the digits starting from least significant and moving on to most significant.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49427

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback