Doesn’t Hillel’s newsletter directly refute this blog post?
The “special virtue” of bubblesort is that each pass leaves each element of the array closer to its final position.
So if you have some processing of an array that becomes faster the closer the array is to being sorted, and you regularly do a iterate over of the array, you can interleave a bubblesort pass together with each iteration and get an average performance boost at a predictable (and low) worst case cost.
I can think of a common case that could benefit from this optimization. Let’s say you have an array of pointers to objects implementing the same interface/virtual class.
You regularly iterate over the array and call the the same virtual method on each object. This becomes faster if the array is sorted by type.
Doesn’t Hillel’s newsletter directly refute this blog post? The “special virtue” of bubblesort is that each pass leaves each element of the array closer to its final position. So if you have some processing of an array that becomes faster the closer the array is to being sorted, and you regularly do a iterate over of the array, you can interleave a bubblesort pass together with each iteration and get an average performance boost at a predictable (and low) worst case cost.
I can think of a common case that could benefit from this optimization. Let’s say you have an array of pointers to objects implementing the same interface/virtual class. You regularly iterate over the array and call the the same virtual method on each object. This becomes faster if the array is sorted by type.