One key to understanding this is that arrays elements ([child.sequence, index]�here) compare on each element when�#<=>�is used, so you're essentially adding the elements index in the array as a secondary sort key. �The call of�#sort_by�and then�#with_index�is chaining enumerators. �(Hopefully I've gotten that basically right; it's not the simplest part of Ruby, but it's fascinating...) �This all allows us to use an unstable (but fast!) sort, while essentially adding additional sort keys that keep it stable.

A shorter version reads:

��def�sort_children2

� ��@children =�@children.sort_by.with_index { |*args| args}

��end

Clever, perhaps, but a little obscure. �This works because�|*args|�stuffs all the arguments into an array, which coincidentally is exactly where we want them.

Here's a fun little piece of code to demonstrate what I'm doing:

# This example is flawed, but hopefully useful for demonstration purposes.

def test_stable_sorting

� ary = (1..100).to_a.shuffle + (1..100).to_a.shuffle

� # This associates an ordering with the randomized numbers

� idx = 0

� paired = ary.collect {|value| [value, idx += 1]}

� puts "Now the numbers are paired; the first is the random number 1-100,"

� puts "the second is its sequence within the 200 entries."

� puts paired.inspect

� puts

� puts "#sort is unstable; you'll see many entries with equal first values"

� puts "where the first of them has a higher second (sequence) number, meaning"

� puts "it's out of order now."

� puts paired.sort {|x,y| x.first <=> y.first }.inspect

� puts

� puts "Now we sort exclusively on the value, while preserving ordering;"

� puts "All entries with identical first values should have second values"

� puts "that are also in numerical order."

� puts paired.sort_by.with_index {|x, i| [x.first, i]}.inspect

end

-- �Morgan

On Sun, Jan 30, 2011 at 5:22 PM, Robert Rice <rice.audio@pobox.com> wrote:

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 <rice.audio@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@lists.macosforge.org
http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel

_______________________________________________
MacRuby-devel mailing list
MacRuby-devel@lists.macosforge.org
http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel

_______________________________________________
MacRuby-devel mailing list
MacRuby-devel@lists.macosforge.org
http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel