Hi Morgan:
Thanks for the info although I have to admit that I don't understand how your
solutions work.
I also needed my sort to return a modified flag to update the file if changed
so I wrote my own bubble sort.
I haven't test this yet:
def sort_children # Don't trust Ruby sort to maintain sequence, also
need set_modified
return if @children.empty?
arr = @children.map{ | child | [ child.sequence, child ]
modified = false
while true # bubble sort
change = false
new_arr = []
arr.each_with_index do | new_child, index |
if index.zero?
prior_child = new_child
new_arr[ 0 ] = new_child
elsif new_child.first <
prior_child.first # OOO
change = true
new_arr.insert( index - 1, new_child )
else
new_arr[ index ] = new_child
prior_child = new_child
end
end
break unless change
modified = true
arr = new_arr
end
return unless modified
@children = arr.map{ | child | child.last }
set_modified()
end
Thanks,
Bob Rice
On Jan 30, 2011, at 7:19 PM, Morgan Schweers wrote:
> 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 <[email protected]> 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
> [email protected]
> http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
>
> _______________________________________________
> MacRuby-devel mailing list
> [email protected]
> http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
_______________________________________________
MacRuby-devel mailing list
[email protected]
http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
