[MacRuby-devel] Ruby sort algorithm

[Morgan Schweers]

Greetings,
Ruby's sort algorithm is quicksort, last I checked, and quicksort is not
stable (which is the property you're looking for in a sort).  There are a
bunch of ways around this, including writing your own, but one cute, quick,
but possibly performance-impairing, approach I've seen (Matz's suggestion)
is:

  n = 0
  ary.sort_by {|x| [x, n += 1]}
Apparently it's also possible in 1.9.x (and thus MacRuby) to do:

  ary.sort_by.with_index {|x, i| [x, i]}

It's not much faster, though.  In the end, I'd probably suggest writing your
own, if the performance of this is too poor.  (One person claimed this was
on the order of 50 times slower; I haven't benchmarked it myself.)
 Mergesort is stable, for example.

This is a common problem; most systems don't need a stable sort, so they use
Quicksort as a 'best general purpose' algorithm.

--  Morgan

On Sun, Jan 30, 2011 at 12:03 PM, Robert Rice <rice.audio at pobox.com> wrote:

> Hi:
>
> Does the Ruby Array sort algorithm maintain the relative position for
> children returning the same value for the comparison? I had an instance
> where two children having the compare value were interchanged.
>
> Thanks,
> Bob Rice
>
> _______________________________________________
> MacRuby-devel mailing list
> MacRuby-devel at lists.macosforge.org
> http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macosforge.org/pipermail/macruby-devel/attachments/20110130/194018e5/attachment.html>