Kids, Code, and Computer Science Magazine

Fisher-Yates Shuffle

Jeremy Thompson on Flickr

What sounds like a country western dance actually is an efficient way to sort large sets of data randomly.

If you need to sort a set of data, and you don’t happen to have the Hogwarts sorting hat, you’ll have to rely instead on algorithms like the Fisher-Yates Shuffle. While it sounds like a type of dance, in fact, it’s a way to sort data with as little bias as possible. Plus it can do much more than sort Hogwarts students into one of four houses.

The Fisher-Yates Shuffle is an algorithm — a set of rules — to shuffle data in an unbiased way. Each result is as likely as any other result.

In 1938, two English statisticians, Sir Ronald Fisher and Frank Yates, worked together to create a set of rules to be done with pen and paper:

Step 1 — Write down numbers from 1 through N. So N could be 100.
Step 2 — Pick a random number k between the numbers 1 and the number of numbers not crossed out in your list in step 1.
Step 3 — Counting from the low end of your list of numbers not crossed out, cross out the kth number not yet struck out then write it down at the end of a separate list of numbers.
Step 4 — Repeat from the second step until all numbers have been crossed out.

The sequence of numbers in the separate list of numbers, in step 3, is now a random permutation of the original list of numbers from step 1.

The modern version of this shuffling algorithm is called Algorith P, from the book, The Art of Computer Programming by Donald Knuth. It simplifies step 3 of the Fisher-Yates Shuffle to reduce time spent by the computer counting numbers left unstruck. The modern version also shuffles in place. Instead of creating a copy of the data set, shuffling is done within the original data.

Of course, the modern version used in programming has more subtleties to make programming easier. For example, what if you do not know the value of N, the highest number in your data set?

 

Become a subscriber and get access to the rest of this article. Plus all our magazine articles.

Stories also include numerous links to help parents, kids, and teachers learn more. Get access today at just $15 per year!

Subscribe Today!

Also In The December 2016 Issue

Hour of Code and EU Code Week are events designed to introduce kids, young adults, and others to programming and computer science.

Real life treasure hunts are a way to get outdoors, learn map skills, and have fun finding hidden caches near you.

A trainable puppy plus treats plus technology equals a dog that can send selfies. Here's how.

An app to help kids remember important stuff like feed your pets, brush your teeth, and smile.

These books include lots of great projects to work on by yourself or with others, from Scratch and Minecraft to fun maker space projects.

The mBot robotics kit is an excellent comparatively low-cost way to begin working with robots.

There are maybe a bazillion Raspberry Pi projects online. Here are really fun projects plus links to find more.

The Wayback Machine lets you travel back in time to see old websites. Plus the Internet Archive has thousands of vintage games, software, books, and more.

Eating dog food doesn't sound like much fun but it's an important part of creating software.

The ability to identify patterns, decompose large problems into small parts, develop algorithms to solve problems, and generalize to find solutions.

To celebrate this wonderful time of the year, let’s create some holiday music using Sonic Pi on our Raspberry Pi.

This project shows how to use the pygame code library to move simple animations with the Python programming language.

This project, shows you how to create your own random password generator in the C# programming language.

These projects mix science and technology in interesting ways. Sewing and electronics, for example, is a different way to learn about electronics.

Links from the bottom of all the December 2016 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for December 2016.

What sounds like a country western dance actually is an efficient way to sort large sets of data randomly.