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

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_misconceptions.html (Bubble sort is not great when your data is almost sorted. Insertion sort is, though.)

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.

The other reply thread is great and has a SmarterBubbleSort implementation -- it's important to note that the early stopping rule is an enhancement, not vanilla bubble sort (I had to learn both, maybe curricula these days jumps straight to the smarter version?), but even so it complicates the implementation and still isn't ever better than vanilla insertion sort.

Here is insertion sort

    void insertion_sort(int s[], int n) {
      int i, j;
      for (i = 1; i < n; i++) {
        for (j = i; j > 0 && s[j] < s[j-1]; j--) {
          swap(&s[j], &s[j-1]);
        }
      }
    }

You can even improve this further (some improvements have new names), however its base form is not in the class of bad algorithms to never use. Besides Bubble sort, Bogosort comes to mind. And there are of course nice algorithms to use if your data works for them, Radix sort comes to mind. Knowing your data is good advice, knowing never to use bubble sort is also good.

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

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.

> 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!"

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.

Bubble sort performs 11 comparisons and 13 memory reads in this case, actually. Because on the first pass through the array it performed a swap, it has to loop through the array a second time to verify the array is completely sorted.

To avoid confusion, here's the bubble sort algorithm:

  procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
        swapped = false
        for i = 1 to n-1 inclusive do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
        n = n - 1
    until not swapped
  end procedure

As you can see, after performing a swap during the first pass through the array it has to go through again (though it can skip the last element because we know the last element must contain the largest element in the array)

Insertion sort will perform 7 comparisons, 1 swap, 7 memory reads and 2 writes.

You can avoid the second pass...

No, you can't, because at the end of the first pass you have no way to know that it is in sorted order. Go ahead and try to write the pseudocode for your bubble sort implementation that avoids the second pass.

To be concrete, the array in order 1235647 has the first six comparisons go the same way as in 1234657, but it doesn't end up sorted in one pass.

Perhaps harry8 was thinking of the bubble sort implementation in the OP, which would indeed stop after one pass in these cases.

you look back and see if you will need a second swap and set your "need another pass" boolean that you named "swapped" accordingly.

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.

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.