Generating random permutations
Jump to navigation
Jump to search
Problem Description
Generating random permutation of an input string.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Sattolo's algorithm (1986) | |
| nlogn | ||
| Linear | Fisher–Yates/Knuth shuffle (1938)
Durstenfeld's Algorithm 235 (1964) [- Radix sorting method (1887)] |
|
| logn |