[MacRuby-devel] Ruby sort algorithm

[Robert Rice]

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 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
> 
> _______________________________________________
> 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/c9963043/attachment.html>