From: Jason Creighton <androflux@...>
Date: 2003-09-18T08:52:06+09:00
Subject: Re: scrambler one-liner

On Wed, 17 Sep 2003 23:02:38 +0900
Michael Campbell <michael_s_campbell@yahoo.com> wrote:

> > [Jason Creighon]:
> > ....but I don't know what evil effects having the comparison be
> > random will have on a sorting algorithm.
> 
> Isn't that the point here?

What I meant was I don't know what evil effects have the comparison
being *volitile* will have on a sorting algorithm. Suppose we have a
sort algoritm that scans the array, swapping out of place elements, and
is done when we do a scan without swapping anything. In other words, a
bubble sort. Like this one:

class Array
  def bubble_sort!(&block)
    block ||= proc { |a,b| a <=> b }
    done = false
    len = length-2
    until done
      done = true
      (0..len).each do |i|
	if block.call(self[i],self[i+1]) == 1
	  p self
	  tmp = self[i]
	  self[i] = self[i+1]
	  self[i+1] = tmp
	  # Why doesn't this work instead of the above?
	  # self[i], self[i+i] = self[i+1], self[i]
	  done = false
	end
      end
    end
    return self
  end
  def bubble_sort(&block)
    self.dup.bubble_sort!(&block)
  end
end

This algoritm depends upon two elements always comparing the same way:
Otherwise it could go on forever, waiting for when we can scan the whole
thing without finding an out of place element. Of course, a bubble
sort for an array with N items only needs N-1 passes (right?) so we
could code that in, but I'm just using this as an example of how using
rand() in sort blocks could confuse algoritms:

>> require 'bubble_sort'
=> true
>> [4,3,2,1].bubble_sort
[4, 3, 2, 1]
[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 1, 3, 4]
=> [1, 2, 3, 4]

Okay, that works fine. Let's try with a rand sort block:

>> [4,3,2,1].bubble_sort { rand <=> 0.5 }
[4, 3, 2, 1]
[4, 3, 1, 2]
=> [4, 1, 3, 2]

Out of sheer luck, after the second swap, we run though the whole array
without rand <=> 0.5 returning 1. Let's try with a larger array:

>> (0..10).to_a.bubble_sort { rand <=> 0.5 }
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 2, 1, 4, 3, 5, 6, 7, 8, 9, 10]
[0, 2, 1, 4, 5, 3, 6, 7, 8, 9, 10]
[0, 2, 1, 4, 5, 3, 6, 7, 9, 8, 10]
[0, 2, 1, 4, 5, 3, 6, 7, 9, 10, 8]
[2, 0, 1, 4, 5, 3, 6, 7, 9, 10, 8]
[2, 1, 0, 4, 5, 3, 6, 7, 9, 10, 8]
[2, 1, 4, 0, 5, 3, 6, 7, 9, 10, 8]
[2, 1, 4, 0, 5, 6, 3, 7, 9, 10, 8]
<hundreds more lines of this>

It would take quite a while to run through a large array this way.

Now, obviously, Array#sort doesn't work this way, otherwise it'd hang on
rand sort blocks. But, as a rule, it's probably not a real good idea to
mess with it that way. #sort_by ensures that any given two elements will
always compare the same way during sorting, so it's probably good to use
that.

.....but I could be totally wrong here.

Jason Creighton