tags:

views:

79

answers:

2

Okay, I have been messing around with different sorting algorithms in Ruby; mainly variations quicksort. I have a version of dual pivoted quicksort that picks random pivots. So when the random pivot lands at the beginning or end of the array weird things start happening. I did some investigating and have boiled it down to this strange phenomenon.

//irb output             #using Ruby 1.8.6 and irb 0.9.5
irb> foo = [1,2,3,4]     #create my array, very generic for an example
=> [1, 2, 3, 4]
irb> foo[0],foo[1],foo[2],foo[3] = foo[1],foo[0],foo[3],foo[2]
=> [2, 1, 4, 3]          #array swaps inside values with edge values fine.
irb> foo
=> [2, 1, 4, 3]          #values have changed correctly.
irb> foo = [1,2,3,4]     #reset values
=> [1, 2, 3, 4]          #next I am going to try and swap the element foo[0] with itself
irb> foo[0],foo[0],foo[2],foo[3] = foo[0],foo[0],foo[3],foo[2]
=> [1, 1, 4, 3]          #for some reason elements foo[0] and foo[1] take on the value of foo[0]
irb> foo     #check our array again
=> [1, 2, 4, 3]          #neither value foo[0] nor foo[1] are altered.

Can anyone explain why this is happening?

Just to be clear, I am not looking for help implementing quicksort.

EDIT: To, hopefully, make the problem clearer here is what the implementation looks like:

# error caused when (pseudo-code) pivot1|pivot2 == start|end
foo[start], foo[pivot1], foo[pivot2], foo[end] = 
    foo[pivot1], foo[start], foo[end], foo[pivot2]
A: 

You've made a type error

foo[0], foo[0] instead of foo[0], foo[1]!

yogsototh
No, he didn't. He's trying to swap for[0] with itself.
Rayne
Scratch that, I read his code wrong. Sorry.
Rayne
I assure you everything is typed correctly. In the implementation of the dual pivot it would look more like this. foo[start], foo[pivot1], foo[pivot2], foo[end] = foo[pivot1], foo[start], foo[end], foo[pivot2] # where start == pivot1
sanscore
Actually, I read it wrong again. You're right. I'm stumped.
Rayne
+7  A: 

Nothing strange here. see my comments below.

=> [1, 2, 3, 4]          
irb> foo[0],foo[0],foo[2],foo[3] = foo[0],foo[0],foo[3],foo[2]

#this is return value from the last expression ,that is the 
#parallel assignment , the value of that expression is [1, 1, 4, 3] , 
#not the value of foo
=> [1, 1, 4, 3]        
irb> foo     

#In the last parallel assignment, you set f[0] to f[0] , did not change f[1] ,
#you swapped f[2],f[3] .This is exactly what you did .
=> [1, 2, 4, 3]
pierr
Ah, I understand. Now I am kicking myself because I should have figured that out on my own. Guess I am back to the drawing board to figure out my problem.
sanscore
I thought the return value of a parallel assignment was the new value of the array. Learn somethin' new every day, huh?
Rayne