3 ms·
OK, but I was kind of hoping for a treatment that involved the workings of one or both algorithms. They are subject to the same theoretical lower bound, yes. Do
by thaumasiotes 2y ago
OK, but I was kind of hoping for a treatment that involved the workings of one or both algorithms. They are subject to the same theoretical lower bound, yes. Do they have any advantages or disadvantages relative to each other? Does one of them do a much better job reaching the theoretical bound?
- orlp 2y agoThis paper goes in way more detail than you'd likely ever want on that topic: https://dl.acm.org/doi/10.1145/3009909 https://dl.acm.org/doi/10.1145/3009909.
- slaymaker1907 2y agoIt kind of makes me mad that the very simple RS algorithm (divide and conquer) isn't more widely known given that it's so easy to implement and that it's actually parallelizable unlike Fisher-Yates. I think it's also better pedagogically since you can easily do it with a deck of cards and a coin or some dice while Fisher-Yates is pretty unwieldy for anything beyond very small lists.