Jason Creighton
9/17/2003 8:39:00 PM
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