Keep Bogo Sort Visualization
Keep Bogo Sort shuffles at random, but every element that lands in the right spot stays there.
How it works
Keep Bogo Sort is Bogo Sort with a memory. After each shuffle it checks every position, and any element that happens to be in its final spot is locked in place. Only the elements that are still wrong get shuffled again.
A random shuffle puts on average one element in its right place, so each round locks about one more, and the whole list is done in roughly n rounds: around n² operations instead of n · n!. It's still a terrible way to sort, but it finishes, and watching the order lock in one piece at a time is oddly satisfying.
What to watch for
Watch the noise slowly freeze into a rainbow, one locked element at a time, until the last few swap into place.
Complexity
- Best
- n
- Average
- n²
- Worst
- ∞
- Extra space
- n
- Stable
- No
Race it
Same shuffle, same speed, one winner: Keep Bogo vs Bogo. Or open the studio to try other layouts, sizes and speeds, and make a video of it.
FAQ
How is Keep Bogo Sort different from Bogo Sort?
Bogo Sort reshuffles everything every time, so its progress is lost. Keep Bogo Sort keeps every element that's already in the right place, so it always makes progress.
Is Keep Bogo Sort a real algorithm?
It's a teaching variant, closely related to ideas like Bozo Sort. It needs to know each element's final position, which is why it's a toy, not a practical sort.
What is the time complexity of Keep Bogo Sort?
About n rounds of shuffling on average, so roughly O(n²) operations.