4 ms·

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 excep

by 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
      > While it probably does, depending on implementation details use more memory Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort. Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[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!"
      - harry8 9y ago
        1,2,3,4,6,5,7 6 comparisons, 1 swap with bubble and it stops. I make it 7 memory reads and 2 memory writes. Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.

by Jach 9y ago

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
    > While it probably does, depending on implementation details use more memory Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort. Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[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!"
    - harry8 9y ago
      1,2,3,4,6,5,7 6 comparisons, 1 swap with bubble and it stops. I make it 7 memory reads and 2 memory writes. Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.