Shuffling algorithms and randomization to improve algorithm‘s runtime.

Shuffling card is an essential part of every card game. There are many techniques for shuffling cards but overhand and riffle are the most popular ones.

Overhand shuffle

In this shuffle, a set of cards are transferred from bottom of the deck to the top of the deck and the same process gets executed recursively.

A deck of cards is essentially a fixed sized array of length 52. Overhand shuffle puts set of cards from the end of the array to the beginning of an array. This process gets repeated to get a good shuffle.

Riffle shuffle

This involves cutting the deck into 2 halves so we get two sets of cards and riffle them such that at the end both halves gets interleaved.

A quick implementation of riffle shuffle would be something like following.

There are shuffling algorithms in existence that runs faster and gives consistent results. These algorithms rely on randomization to generate a unique random number on each iteration.

As per Wikipedia

If a computer has access to purely random numbers, it is capable of generating a "perfect shuffle".

Fisher-Yates shuffle is one such algorithm for achieving a perfect shuffle using a random number generator. The algorithm is named after Ronald Fisher and Frank Yates who first described this algorithm in their book in 1938. Later Donal Knuth and Richard Durstenfeld introduced an improved version of the algorithm in 1964.

Unlike swapping items at two different indexes, algorithm generates a random number k between range of the elements inside an array. Every iteration updates the last element in the range thus random generator works on the new range on every iteration and generates a unique number every time.

Above algorithm works in linear time and faster than riffle shuffle. Putting some timing around both shuffle algorithm for an array of 100 integers produces below result.

Programming languages use a similar algorithm in their inbuilt implementation of shuffle method. Java's implementation of shuffle method could be used by invoking

collections.shuffle()

To shuffle a linked list which doesn't allow access of object by their index, Java converts it back to array first so to have random access, shuffles it and converts it back to list.

Shuffle method's implementation From Java docs

Can randomization improve the runtime of an algorithm.

A good shuffling algorithm has a function which generates a unique random number consistently. Quicksort which gives quadratic time performance on a sorted array can generate consistent O(nlogn) result by randomizing sorted array first and then fed it into quicksort algorithm.

There are two different types of randomization algorithms namely Las Vegas and Monte Carlo algorithms. IMHO, one can't get a better name than Las Vegas for a shuffling algorithm :)

Las Vegas algorithm guarantees to give result in an expense of the time complexity whereas Monte Carlo compromises guarantee of the result by exiting early if it doesn’t find the desired output. If we have to search an item inside an array Las Vegas algorithm will execute until it finds the expected item whereas Monte Carlo will execute for a couple of cycles and stops if it doesn't find the item. Rabin Karp algorithm for string searching uses Las Vegas algorithm to find all matching sub-string inside input string.

Applications

Randomized algorithms are useful in applications that require good results consistently irrespective of input to the algorithms. Software in rockets, satellites, airplane, cryptography utilizes randomization to get a high probability of good result on algorithm

Resources

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
https://www.geeksforgeeks.org/randomized-algorithms-set-2-classification-and-applications/

Images are taken from Google.

Conclusion

There is so much to learn and write about shuffling algorithms and randomization. In my next post, we'll sort back cards after shuffling them in here using inbuilt sort function in language.

If you want me to write on a specific topic, please feel free to post them in the comment section below.

You can support my work by buying me a coffee below. 💚💚💚💚💚💚 !!