Random Select using Fisher Yates algorithm

Today, I had a chance to use Fisher Yates algorithm. Here is the problem statement:

Out of an array of N items, randomly pick K items where 0 < K < N.

My first version of the algorithm was as follows:

The code above has two problems:

  1. When n == k, the loop takes a long time to complete.
  2. When k > n, the loop does not terminate.

After a bit of search, I landed up in Fisher Yates shuffle algorithm. A slightly modified version that terminates the loop a bit earlier is given below.

The code above is self-explanatory. The last k items in the array are shuffled. The algorithm runs in O(n2) when n = k. But, runs much faster when k is much smaller than N.

Leave a Reply

Your email address will not be published. Required fields are marked *