Re:“It is never a compiler error”
by openasocket on Tuesday November 14, 2017 @09:50PM
(#15701125)
> Others have pointed out that bubble sort is great when your data is already mostly sorted
It really isn't, compared to insertion sort.
https://users.cs.duke.edu/~ola/papers/bubble.pdf shows insertion sort performs 5x better. I also like Knuth's Quote in TAOCP: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
> running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching
Name one sorting algorithm that doesn't involve purely running sequentially through contiguous memory.
It really isn't, compared to insertion sort. https://users.cs.duke.edu/~ola/papers/bubble.pdf shows insertion sort performs 5x better. I also like Knuth's Quote in TAOCP: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
> running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching
Name one sorting algorithm that doesn't involve purely running sequentially through contiguous memory.