Implementing Fisher-Yates shuffling algorithm

3

Index

Stats

8,298 visits, 17,816 views

Tools

Translations

This tutorial hasn't been translated.

License

This tutorial is licensed under CC BY 4.0. Please refer to the license text if you wish to reuse, share or remix the content contained within this tutorial.

Published on 14 Feb, 2013. Last updated 19 Feb, 2019

Now we are getting to the main algorithm.

To shuffle an array a of n elements (indices 0..n-1):

for i from n − 1 downto 1 do

j ← random integer with 0 ≤ j ≤ i

exchange a[j] and a

Add 2 more variables to use in algorithm. I used "k" instead of "j" to see more clearly. And to exchange values of two array values we need a temporary variable.

For loop does not support decreasing values, instead of it i used a while loop. Add a new "system-while" event.

Add another condition for stopping "while"

. If loop reaches to 1, it will stop.

We have a condition, but our loop is a infinite loop at now. Because "i" value is still the same. We have to decrease it, at the end. But first we will pick a random value with k to exchange. Add a "System-set value" action

UPDATE: There is an error in picture random(i+1) can give a value like i,999999 so using a function like int(floor(random(i+1))) is better idea

  • 2 Comments

  • Order by
Want to leave a comment? Login or Register an account!