Quicksort vs. Shell

[Claudio L.]

(06-17-2014 06:53 PM)Werner Wrote:  

(06-17-2014 03:03 PM)Claudio L. Wrote:  Shell sort seems to be the fastest of the insertion methods (better than binary insertion, as suggested by Walter). Shell is also one of the simplest to implement, that's why I chose it for this comparison.

You were specifically talking about RPL, and believe me, there's no beating simple binary insertion in RPL. Shell sort may not be hard to implement in regular languages, but in RPL it is at least an order of magnitude harder than implementing binary insertion, as is Quicksort.

Werner

Maybe I wasn't clear in my post. The purpose was to sort lists in RPL, I didn't say the algorithm was going to be written in RPL. The project I'm working on is precisely reimplementing all RPL commands in C.
Binary insertion is still a very good algorithm for small sets. Shell is just an improvement over the standard insertion to "extend its life" to larger sets.
Now you made me wonder: what would happen if we use binary insertion instead of plain insertion on each gap run? I can't find anybody investigating that, so it's probably a bad idea, but would be nice to know.

BTW: Sorry I renamed you Walter in one of my posts above, I fixed that.