3 ms·

I think we need to get away from this attitude, that I used to hold, that O() is everything. It isn't. It isn't even close. We should instead wonder why an algo

by harry8 9y ago

I think we need to get away from this attitude, that I used to hold, that O() is everything. It isn't. It isn't even close. We should instead wonder why an algorithm was chosen without regard for the nature of the data on which it will be applied. For sorting O(n lg n) only makes sense as a selection criteria if you have absolutely no idea about what data is being sorted. Why is that? If the answer is you just don't care about the perfromance and can say why it isn't important (at least yet) as long as you avoid the pathological then that's a good answer. It's a really bad answer to assume it when you can't. IMHO. Others have pointed out that bubble sort is great when your data is already mostly sorted. The textbook example is check stub ids, which are sequential - probably an outdated example nowadays. The benefit is greater than a O() analysis would have you believe because running sequentially through contiguous memory is something computers are just great at doing due to memory caching and prefetching. Minimising cache misses /may/ dominate the number of passes of the data in performance analysis. If you don't care about performance then an O(N^2) algorithm may be also something you don't care about.

wilun 9y ago
Hu. Bubble Sort. And not only that; a buggy version! And if you believe sequential access is gonna save you from O()... you're so wrong its not even funny. Of course the curves will cross latter. But they will cross. Especially on a sort.
- harry8 9y ago
  I'm not sure you've demonstrated anything here about the topic under discussion. You might like to try achieve a better result around here, people tend to appreciate it.
Jach 9y ago
You're misidentifying the attitude. The problem is that Bubble Sort is a terrible algorithm, there's no reason not to use Insertion Sort or better instead except for some reason CS programs still inflict BS on students so that's what they remember when they just need to sort something. http://warp.povusers.org/grrr/bubblesort_eng.html http://warp.povusers.org/grrr/bubblesort_eng.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html (Bubble sort is not great when your data is almost sorted. Insertion sort is, though.)
- harry8 9y ago
  To the second link "Bubble sort always performs n-1 passes through the data (where n is the amount of elements), and it always performs (n-1)+(n-2)+...+1 comparisons regardless of how the data is organized to begin with." That is just false. 1 pass and n-1 comparisons then stops for already sorted data is what you get. An implementation that doesn't show that characteristic has been either deliberately or accidentally pessimized to behave poorly. You can gimp any algo to make it look bad. Quicksort without randomization on a pathological case is O(n^2) for example and nobody cares for the overwhelming majority of practical purposes. If your definition of bubble sort is that it must be O(n^2) always then we're not using "bubble sort" to mean the same thing and it's pointless to continue the discussion. Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? You pay for additional copies in both space and cpu cycles. 2xn space for selection usually - but maybe this can be avoided without paying a very high time overhead, (eg find the spot, ripple all data below the spot down to the hole where you selected to open a slot for insert or similar). Count the memory operations, ie number of memory reads and number of memory writes for a given set of data comparing the two algorithms. Suggestions: Write 50 odd lines of C code to see the actual effect in cpu cycles. Craft data to make each algorithm dominate the other, it's really interesting to see. I'm disinclined to say "Never uses algo X, always use algo Y!" Because it's really hard for that to be sensible given all the various shapes and sizes input data takes. Know your data is always really, really good advice.
  - openasocket 9y ago
    > Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? What about insertion sort? Which always performs fewer comparisons and swaps than bubble sort for any array, by the way.
    - harry8 9y ago
      So I made the case with evidence that it doesn't always perform fewer comparisons and it it doesn't always perform fewer swaps. While it probably does, depending on implementation details use more memory. Do feel free to actually make your case with evidence, that I would be interested in reading. What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.
openasocket 9y ago
> 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 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.

by harry8 9y ago

wilun 9y ago

Hu. Bubble Sort. And not only that; a buggy version! And if you believe sequential access is gonna save you from O()... you're so wrong its not even funny. Of course the curves will cross latter. But they will cross. Especially on a sort.

harry8 9y ago
I'm not sure you've demonstrated anything here about the topic under discussion. You might like to try achieve a better result around here, people tend to appreciate it.

Jach 9y ago

You're misidentifying the attitude. The problem is that Bubble Sort is a terrible algorithm, there's no reason not to use Insertion Sort or better instead except for some reason CS programs still inflict BS on students so that's what they remember when they just need to sort something. http://warp.povusers.org/grrr/bubblesort_eng.html http://warp.povusers.org/grrr/bubblesort_eng.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html (Bubble sort is not great when your data is almost sorted. Insertion sort is, though.)

harry8 9y ago
To the second link "Bubble sort always performs n-1 passes through the data (where n is the amount of elements), and it always performs (n-1)+(n-2)+...+1 comparisons regardless of how the data is organized to begin with." That is just false. 1 pass and n-1 comparisons then stops for already sorted data is what you get. An implementation that doesn't show that characteristic has been either deliberately or accidentally pessimized to behave poorly. You can gimp any algo to make it look bad. Quicksort without randomization on a pathological case is O(n^2) for example and nobody cares for the overwhelming majority of practical purposes. If your definition of bubble sort is that it must be O(n^2) always then we're not using "bubble sort" to mean the same thing and it's pointless to continue the discussion. Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? You pay for additional copies in both space and cpu cycles. 2xn space for selection usually - but maybe this can be avoided without paying a very high time overhead, (eg find the spot, ripple all data below the spot down to the hole where you selected to open a slot for insert or similar). Count the memory operations, ie number of memory reads and number of memory writes for a given set of data comparing the two algorithms. Suggestions: Write 50 odd lines of C code to see the actual effect in cpu cycles. Craft data to make each algorithm dominate the other, it's really interesting to see. I'm disinclined to say "Never uses algo X, always use algo Y!" Because it's really hard for that to be sensible given all the various shapes and sizes input data takes. Know your data is always really, really good advice.
- openasocket 9y ago
  > Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? What about insertion sort? Which always performs fewer comparisons and swaps than bubble sort for any array, by the way.
  - harry8 9y ago
    So I made the case with evidence that it doesn't always perform fewer comparisons and it it doesn't always perform fewer swaps. While it probably does, depending on implementation details use more memory. Do feel free to actually make your case with evidence, that I would be interested in reading. What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.

openasocket 9y ago

> 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 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.