Forum: Ruby Implementation of the object.sort method.

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
84d2933d3d46ebe5f3a4983da4c73831?d=identicon&s=25 tsu tsu (jbucaran)
on 2007-05-09 05:54
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.
6087a044557d6b59ab52e7dd20f94da8?d=identicon&s=25 Peña, Botp (Guest)
on 2007-05-09 06:53
(Received via mailing list)
On Behalf Of Jorge Domenico Bucaran Romano:
# [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
852a62a28f1de229dc861ce903b07a60?d=identicon&s=25 Gavin Kistner (phrogz)
on 2007-05-09 07:00
(Received via mailing list)
On May 8, 9:54 pm, Jorge Domenico Bucaran Romano <jbuca...@gmail.com>
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
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2007-05-09 10:19
(Received via mailing list)
On 5/9/07, Jorge Domenico Bucaran Romano <jbucaran@gmail.com> 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
84d2933d3d46ebe5f3a4983da4c73831?d=identicon&s=25 tsu tsu (jbucaran)
on 2007-05-09 16: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
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2007-05-09 16:35
(Received via mailing list)
On 09.05.2007 16:01, Jorge Domenico Bucaran Romano 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
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2007-05-09 16:41
(Received via mailing list)
On Wed, 09 May 2007 12:54:26 +0900, Jorge Domenico Bucaran Romano 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.
E7559e558ececa67c40f452483b9ac8c?d=identicon&s=25 Gary Wright (Guest)
on 2007-05-09 16:41
(Received via mailing list)
On May 9, 2007, at 10:01 AM, Jorge Domenico Bucaran Romano 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 Wright
8b97d36adf7291c186c1fcbf9848e0cb?d=identicon&s=25 Calamitas (Guest)
on 2007-05-09 16:45
(Received via mailing list)
On 5/9/07, Jorge Domenico Bucaran Romano <jbucaran@gmail.com> 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
753dcb78b3a3651127665da4bed3c782?d=identicon&s=25 Brian Candler (Guest)
on 2007-05-09 17:03
(Received via mailing list)
On Wed, May 09, 2007 at 11:01:58PM +0900, Jorge Domenico Bucaran Romano
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.
84d2933d3d46ebe5f3a4983da4c73831?d=identicon&s=25 tsu tsu (jbucaran)
on 2007-05-09 17: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
This topic is locked and can not be replied to.