Random shuffle algorithm

To shuffle an array a of n elements:
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]

This algorithm is used to solve problems like:
Given an array, one has to replace its elements in such a way that no element is at its original place and the placement has to be random.

Wiki article for shuffling algorithm: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle


Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely. In other words, given a deck of cards, how can you shuffle them such that any permutation of cards is equally likely?
Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time.