Algorithm

for i = 0 to n-2 do {
	j <- random integer such that 0 <= j < n
	swap(a[i], a[j])
}

The “inside-out” Algorithm

for i = 0 to n-1 do {
	j <- random integer such that 0 <= j <= i
	swap(a[i], a[j])
}

The advantage of this technique is that n, the number of elements in the array, does not need to be known in advance

Proof

TODO

Properties

Time complexity:

WorstAverageBest

Space complexity auxiliary:

WorstAverageBest

Online: Yes, for “inside-out” version

References