# Shuffling algorithms and randomization to improve algorithm‘s runtime.

Aug 7, 2018 · 4 min read

Shuffling cards 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 array. This process gets repeated to get a good shuffle.

Riffle shuffle

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

There are shuffling algorithms in existence that runs faster and gives consistent results. These algorithms relies 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 random number generator. 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 improved version of the algorithm in 1964.

Unlike swapping items at two different index, 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 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 similar algorithm in their inbuilt implementation of shuffle method. Java’s implementation of shuffle method could be used by invoking

To shuffle a linked list which doesn’t not 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.

## Can randomization improve runtime of an algorithm.

A good shuffling algorithm has a function which generates a unique random number consistently. Quick sort which gives quadratic time performance on sorted array can generate consistent O(nlogn) result by randomizing sorted array first and then fed it into quick sort 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 expense of the time complexity whereas Monte Carlo compromises guarantee of 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 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 requires good results consistently irrespective of input to the algorithms. Software in rockets, satellites, airplane, cryptography utilizes randomization to get high probability of good result on algorithm

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

Stay tuned :)

## Nerd For Tech

From Confusion to Clarification

## Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Written by

## AWDESH

Learner, Philomath. Engineer by choice, humorous by nature. Big fan of technology.

## Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.