Quicksort vs. Shell

[Claudio L.]

(06-18-2014 12:27 PM)David Hayden Wrote:  

(06-16-2014 09:38 PM)Claudio L. Wrote:  Quicksort is theoretically faster for large sets, but that wouldn't apply to calculators, where we are talking of sorting lists with a few objects.

What are the requirements? Since we're talking about small sets, the speed difference may be negligible. In that case, code size may be more important.

Also, should we guarantee that the sort is stable?

Dave

That's a good point. The speed difference between Shell and Quicksort seems to be around 30% to 80 % longer time for Shell, for lists up to 5000 elements (which is what I could find on the internet). However, for 20 to 50 elements we won't even be able to measure the difference.
As of now, we don't know how long it will take the 50g to sort a 1000 element list, considering the RPL overhead, so how do we know if the difference in speed is negligible?

I found this:
http://www.hpcalc.org/details.php?id=2828

It's a quicksort implementation written by Werner (is it the same Werner that prefers binary insertion? if so, what made you change your mind over the years?)
It's implemented in Saturn assembly, and somebody clocked 0.58 seconds for 1000 elements on a 50g. Considering a significant speedup due to ARM C, you might be right: we don't need to worry about speed that much.

Regarding stability... do we really need to? Doesn't matter for sorting numbers. It might matter if sorting some kind of custom list with data (same key but different content). On the other hand, we can make any method stable by introducing the original order as a secondary sorting index. Since we'll be sorting pointers to objects within the same list, the pointers themselves have the original order of the elements. If an element is equal to other, we can compare their pointers, and pick the lowest pointer as the lowest element. That won't add much overhead and needs no extra memory.

Claudio