# Shuffling

Shuffling is a procedure used to randomize an array.

The key property is that each item should have an equal probability to end up in any index.

## Solution

The recommended (simple) algorithm is the `Fisher–Yates shuffle`

. Its time complexity is `O(n)`

. It can even be done *inplace*.

You go from `0 - (n-1)`

and at each index `i`

pick a random number between `0`

- `n-i`

and move the element at the result into the `i + thisRandomNumber`

th location in the array.

### Maintains Key Property

It maintains that key property as:

```
Probablility any item makes it to the first position
= 1/n
Probablility any item makes it into the second position
= didn't make it into the first * makes it into the second
= (n-1)/(n) * 1/(n-1) = 1/n
... so on
```

### Has complexity `O(n)`

Remember random number generation / assiging an item to an array is `O(1)`

, so its just `n`

iteration of `O(1)`

### Code

```
function shuffleInPlace<T>(array: T[]): T[] {
// if it's 1 or 0 items, just return
if (array.length <= 1) return array;
// For each index in array
for (let i = 0; i < array.length; i++) {
// choose a random not-yet-placed item to place there
// must be an item AFTER the current item, because the stuff
// before has all already been placed
const randomChoiceIndex = getRandom(i, array.length - 1);
// place our random choice in the spot by swapping
[array[i], array[randomChoiceIndex]] = [array[randomChoiceIndex], array[i]];
}
return array;
}
```