Hi, Can you show me an implementation of the Array.sort method? This implementation would be demonstrative only. This would handle when a block is passed. The reason is I have trouble understanding why the following code works as expected: [3,2,1,4].sort do |a,b| a <=> b end I know it will sort my array but I don't understand the way this method works because other tests I have made bring none results. Regards, Jorge.

on 2007-05-09 07:54

on 2007-05-09 08:53

On Behalf Of Jorge Domenico Bucaran R.: # [3,2,1,4].sort do |a,b| # a <=> b # end botp@pc4all:~$ qri array#sort ------------------------------------------------------------- Array#sort array.sort -> an_array array.sort {| a,b | block } -> an_array ------------------------------------------------------------------------ Returns a new array created by sorting self. Comparisons for the sort will be done using the <=> operator or using an optional code block. The block implements a comparison between a and b, returning -1, 0, or +1. See also Enumerable#sort_by. a = [ "d", "a", "e", "c", "b" ] a.sort #=> ["a", "b", "c", "d", "e"] a.sort {|x,y| y <=> x } #=> ["e", "d", "c", "b", "a"] and irb(main):023:0> a => ["d", "a", "e", "c", "b"] irb(main):024:0> a.sort do |x,y| irb(main):025:1* case irb(main):026:2* when x == "b" irb(main):027:2> -1 irb(main):028:2> when x == "c" irb(main):029:2> 1 irb(main):030:2> else irb(main):031:2* x <=> y irb(main):032:2> end irb(main):033:1> end => ["b", "a", "d", "e", "c"] irb(main):034:0> here we are giving special treatments to "b" and "c", where "b" always come first in comparison while "c" always come last. The rest of the elements follow the normal comparison using the <=> op. # I know it will sort my array but I don't understand the way # this method # works because other tests I have made bring none results. pls post problem codes/results so everyone may help. kind regards -botp

on 2007-05-09 09:00

On May 8, 9:54 pm, Jorge Domenico Bucaran R. <removed_email_address@domain.invalid> wrote: > Can you show me an implementation of the Array.sort method? Slim:~ gkistner$ cd /usr/local/src/ruby-1.8.5-p12/ Slim:/usr/local/src/ruby-1.8.5-p12 gkistner$ cat array.c [...snip...] VALUE rb_ary_sort(ary) VALUE ary; { ary = rb_ary_dup(ary); rb_ary_sort_bang(ary); return ary; } [...snip...] VALUE rb_ary_sort_bang(ary) VALUE ary; { rb_ary_modify(ary); if (RARRAY(ary)->len > 1) { FL_SET(ary, ARY_TMPLOCK); /* prohibit modification during sort */ rb_ensure(sort_internal, ary, sort_unlock, ary); } return ary; } [...snip...] static VALUE sort_internal(ary) VALUE ary; { struct ary_sort_data data; data.ary = ary; data.ptr = RARRAY(ary)->ptr; data.len = RARRAY(ary)->len; qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE), rb_block_given_p()?sort_1:sort_2, &data); return ary; } [...snip...] static int sort_1(a, b, data) VALUE *a, *b; struct ary_sort_data *data; { VALUE retval = rb_yield_values(2, *a, *b); int n; n = rb_cmpint(retval, *a, *b); ary_sort_check(data); return n; } There's your implementation. I suspect that's not what you wanted. Could you try asking your question again using different words? Perhaps then I will understand how to help you. Does it help if you know what the Quicksort[1] algorithm is? [1] http://en.wikipedia.org/wiki/Quicksort

on 2007-05-09 12:19

On 5/9/07, Jorge Domenico Bucaran R. <removed_email_address@domain.invalid> wrote: > > I know it will sort my array but I don't understand the way this method > works because other tests I have made bring none results. > > Regards, Jorge. > Actually you do not need to know anything about the implementation. Ruby uses a modified Quicksort as Phrogz pointed out. The block is just delivering the operation *every* sorting algorithm must eventually apply, "comparison". The result of the block applied to two arbitrary elements of the array (assigned to the parameters a and b) will determine if the LHS is smaller, equal or greater than the RHS. (depending on the values <0, 0 or >0 respectively). If you use the variation #sort_by the block will be applied to both elements first and the results of these applications are compared than (using <=> if I am not mistaken ). If you understand the differnce bewteen a.sort{ rand } and a.sort_by{ rand } you have grasped the concept. HTH Robert

on 2007-05-09 18:01

Hi, I want a demonstrative implementation of the sort method to see how the callback (passed block) is handled, specifically the comparison result <=>. For example, in the following code: puts [4,5,3,2,1].sort do |a,b| -1 end puts [4,5,3,2,1].sort do |a,b| 1 end Both print the array sorted down up. I don't understand how this is possible so I wanted to see a demonstrative (but factual) implementation of the sort method to see how this parameters are handled. Regards, Jorge

on 2007-05-09 18:35

On 09.05.2007 16:01, Jorge Domenico Bucaran R. wrote: > end > > puts [4,5,3,2,1].sort do |a,b| > 1 > end > > Both print the array sorted down up. I don't understand how this is > possible so I wanted to see a demonstrative (but factual) implementation > of the sort method to see how this parameters are handled. Basically since you do not used block parameters in calculating the block result you cannot expect any particular order. The same code might yield a different ordering with the next version of Ruby because the result is just determined in what order the engine passes pairs to the block. Kind regards robert

on 2007-05-09 18:41

On Wed, 09 May 2007 12:54:26 +0900, Jorge Domenico Bucaran R. wrote: > > I know it will sort my array but I don't understand the way this method > works because other tests I have made bring none results. > > Regards, Jorge. You begin by taking an ordinary sorting algorithm, such as the Quicksort algorithm given at http://yagni.com/combsort/#ruby-inplace-quicksort You will notice it uses the < operator for comparison. The semantics of the <=> (spaceship) operator are such that a<b is equivalent to (a<=>b)<0 and that a<=b is equivalent to (a<=>b)<=0. Once you have made that substitution in the code, you have def partition(a, first, last) pivot = a[first] lastS1 = first firstUnknown = first + 1 while firstUnknown <= last do if (a[firstUnknown] <=> pivot) < 0 ##this is the only change lastS1 += 1 a.swap(firstUnknown, lastS1) end firstUnknown += 1 end a.swap(first, lastS1) lastS1 end def quicksort(a, first = 0, last = a.size - 1) if first < last pivotIndex = partition(a, first, last) quicksort(a, first, pivotIndex - 1) quicksort(a, pivotIndex + 1, last) end end Once you have done this, you can replace the <=> operator with an equivalent call to a block, as follows: def partition(a, first, last, &block) pivot = a[first] lastS1 = first firstUnknown = first + 1 while firstUnknown <= last do if (block.call(a[firstUnknown], pivot)) < 0 lastS1 += 1 a.swap(firstUnknown, lastS1) end firstUnknown += 1 end a.swap(first, lastS1) lastS1 end def quicksort(a, first = 0, last = a.size - 1, &block) return quicksort(a,first,last){|a,b| a<=>b} unless block_given? if first < last pivotIndex = partition(a, first, last, &block) quicksort(a, first, pivotIndex - 1, &block) quicksort(a, pivotIndex + 1, last, &block) end end I hope this helps.

on 2007-05-09 18:41

On May 9, 2007, at 10:01 AM, Jorge Domenico Bucaran R. wrote: > I want a demonstrative implementation of the sort method to see how > the > callback (passed block) is handled, specifically the comparison result > <=>. Sorting is a *big* topic. Ultimately though it comes down to comparing two elements in the array and then rearranging those elements based on the result. As the algorithm proceeds it compares different pairs of items until the list is completely sorted. The common thread among all sorting algorithms is the need to decide the order between two elements and this is the purpose of the block provided to #sort: [4,1,2,3].sort { |a,b| a <=> b } # => [1, 2, 3, 4] [4,1,2,3].sort { |a,b| b <=> a } # => [4, 3, 2, 1] So whenever sort needs to know the ordering of two objects, a and b, its calls out to the block for the answer. If the block returns -1 then a is considered 'less than' b, 0 means they are equal, and 1 means that a is 'greater than' b. The block will be called *many* times during the sort operations: [4,1,2,3].sort { |a,b| puts "#{a}, #{b}"; a <=> b } output: 4, 2 2, 3 4, 3 1, 3 2, 1 By using a block to compare the two items it allows the sorting order to be based on whatever criteria is desired--as long as the block returns -1, 0, or 1 the algorithm can figure the rest out. It isn't clear if you are interested in the sorting algorithm itself, the mechanism by which the block is called and its result used or something else entirely but maybe I've provided enough information that you can clarify your interest. Gary W.

on 2007-05-09 18:45

On 5/9/07, Jorge Domenico Bucaran R. <removed_email_address@domain.invalid> wrote: > end > > puts [4,5,3,2,1].sort do |a,b| > 1 > end > > Both print the array sorted down up. I don't understand how this is > possible so I wanted to see a demonstrative (but factual) implementation > of the sort method to see how this parameters are handled. The block binds to the call to puts and not to the call to sort, or in other words the above is equivalent to: puts([4,5,3,2,1].sort) do |a,b| -1 end You can use parentheses to disambiguate, or use curly braces: puts( [4,5,3,2,1].sort do -1 end ) puts [4,5,3,2,1].sort { -1 } puts( [4,5,3,2,1].sort { -1 } ) Peter

on 2007-05-09 19:03

On Wed, May 09, 2007 at 11:01:58PM +0900, Jorge Domenico Bucaran R. wrote: > puts [4,5,3,2,1].sort do |a,b| > 1 > end > > Both print the array sorted down up. I don't understand how this is > possible It's an artefact of the quicksort algorithm. If you lie to it about how the elements compare, as you are doing above, then you'll get strange results. > so I wanted to see a demonstrative (but factual) implementation > of the sort method to see how this parameters are handled. # Noddy sort def mysort(arr, &blk) blk ||= proc { |a,b| a <=> b } # default if no block passed (0...arr.size-1).each do |i| (i+1...arr.size).each do |j| arr[i],arr[j] = arr[j],arr[i] if blk.call(arr[i],arr[j]) > 0 end end arr end p mysort([4,5,3,2,1]) { |a,b| puts "Comparing #{a} and #{b}"; a <=> b } Please don't use this as an example of a good sort algorithm! But it shows how to do callbacks. B.

on 2007-05-09 19:52

Hi, Thank you all for the replies and useful help. I came up with my demo code. class Array def my_sort if not block_given? return self.sort! end (0...self.size).each do |i| (i+1...self.size).each do |k| self[i], self[k] = self[k], self[i] if yield(self[i],self[k]) > 0 end end self end end puts( [5,9,6,7,8,1,3,2,4,0].my_sort {|a,b| a <=> b}) Now it makes sense. Regars, Jorge