From: Ken Bloom <kbloom@...>
Date: 2007-05-09T23:40:03+09:00
Subject: Re: Implementation of the object.sort method.

On Wed, 09 May 2007 12:54:26 +0900, Jorge Domenico Bucaran Romano wrote:

> 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.

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.

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/