…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?
···
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
Just for the record, I wrote a detailed explanation of the final
one-liner by Kurt M. Dresner in my diary at Advogato:
http://advogato.org/person/fxn/diary.html?start=238
Hey, this thread was exciting :-).
– fxn
[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]
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
···
On Wed, 17 Sep 2003 23:02:38 +0900 Michael Campbell michael_s_campbell@yahoo.com wrote:
Hey, I’m a celebrity!
What a great birthday gift - thank you fxn!
-Kurt
···
On Wed, Sep 17, 2003 at 11:35:41PM +0900, Xavier Noria wrote:
Just for the record, I wrote a detailed explanation of the final
one-liner by Kurt M. Dresner in my diary at Advogato:http://advogato.org/person/fxn/diary.html?start=238Hey, this thread was exciting :-).
– fxn
======= End of Original Message =======<
Hi –
···
On Thu, 18 Sep 2003, Jason Creighton wrote:
# Why doesn't this work instead of the above? # self[i], self[i+i] = self[i+1], self[i]
Because you’ve got i+i instead of i+1 
David
–
David Alan Black
home: dblack@superlink.net
work: blackdav@shu.edu
Web: http://pirate.shu.edu/~blackdav
[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.
…
…but I could be totally wrong here.
No, you’re right, but as was mentioned earlier, some bubble sorts
use the “no swap done” as the ONLY end condition, though to be fair,
when I studied such things, I don’t ever remember seeing one that
did; all I’d ever seen were ones that bubbled through the list n-1
times, and optimized an additional, early end condition of “no swap done”.
···
— Jason Creighton androflux@softhome.net.remove.to.reply wrote:
On Wed, 17 Sep 2003 23:02:38 +0900 > Michael Campbell michael_s_campbell@yahoo.com wrote:
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
The sound you hear is me, banging my head against the wall.
Jason Creighton
···
On Thu, 18 Sep 2003 10:49:55 +0900 dblack@superlink.net wrote:
Hi –
On Thu, 18 Sep 2003, Jason Creighton wrote:
# Why doesn't this work instead of the above? # self[i], self[i+i] = self[i+1], self[i]Because you’ve got i+i instead of i+1