2009-10-08 7 views
0

Bon, j'ai essayé différents algorithmes de tri dans Ruby; principalement des variations de quicksort. J'ai une version de quicksort à double pivot qui choisit des pivots aléatoires. Ainsi, lorsque le pivot aléatoire arrive au début ou à la fin du tableau, des choses étranges commencent à se produire. J'ai fait quelques recherches et je l'ai ramené à ce phénomène étrange.RUBY: Problème étrange avec les tableaux et l'assignation parallèle

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

Quelqu'un peut-il expliquer pourquoi cela se produit?

Pour être clair, je ne cherche pas d'aide pour la mise en place de quicksort.

EDIT: Pour, nous l'espérons, rendre le problème plus clairement voici ce qui semble la mise en œuvre comme:

# 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] 

Répondre

7

Rien d'étrange ici. voir mes commentaires ci-dessous.

=> [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]  
+0

Ah, je comprends. Maintenant, je me donne des coups de pied parce que j'aurais dû me débrouiller tout seul. Je suppose que je suis de retour à la planche à dessin pour comprendre mon problème. – sanscore

+0

Je pensais que la valeur de retour d'une assignation parallèle était la nouvelle valeur du tableau. Apprendre quelque chose de nouveau tous les jours, hein? – Rayne

-1

Vous avez fait une erreur de type

foo [0], foo [ 0] au lieu de foo [0], foo [1]!

+0

Non, il ne l'a pas fait. Il essaie d'échanger [0] avec lui-même. – Rayne

+0

Scratch que, j'ai lu son code faux. Pardon. – Rayne

+0

Je vous assure que tout est correctement tapé. Dans la mise en œuvre du double pivot, cela ressemblerait plus à ceci. foo [début], foo [pivot1], foo [pivot2], foo [fin] = foo [pivot1], foo [début], foo [fin], foo [pivot2] # où début == pivot1 – sanscore