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
Properties
Time complexity:
Worst | Average | Best |
---|---|---|
Space complexity auxiliary:
Worst | Average | Best |
---|---|---|
Online: Yes, for “inside-out” version