4 ms·

Yes. Bubble sort is the comparison of every pair. If you compare only adjacent pairs, you eliminate an enormous number of redundant comparisons. This is bubb

Yes. Bubble sort is the comparison of every pair. If you compare only adjacent pairs, you eliminate an enormous number of redundant comparisons. This is bubble sort without the redundancy elimination. It's just that the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm.

recursive 5y ago
Bubble sort will not make any changes to a sorted array. It's a similar number of comparisons. They're just different ones.
- JohnHaugeland 5y ago
  It's a radically different number of comparisons Bubble sort scans the full array repeatedly until finished, but only along the pairwise edge, and usually finishes way early So in an array of 20 elements you have a maximum of 380 comparisons This searches Euler's Little Triangle the whole way every time, so in an array of 20 elements, you have a maximum of 380 comparisons again Seems similar, right? Except doing pairwise you're likely to exit without doing all 19 scans - at the logarithm if it's well distributed - so it probably does either 4 or 5 scans, saving ~80% of the work The issue isn't the ceiling; it's the common floor Doing it the seemingly-normal way radically changes the common floor
  - recursive 5y ago
    Thank you for making my point. So not only does this do different comparisons, it "radically" changes the number of "common floor" work. And by the way, there's something wrong with your analysis of the number of scans needed for the 20 element bubble sort. I don't understand your argument, but I did some experiments with a randomly distributed array. I never saw it sort in fewer than 12 scans, after a few dozen trials.
ColinWright 5y ago
> Bubble sort is the comparison of every pair. I'm not sure what you mean here, but it seems like you're saying that bubble sort has every pair compared with every other pair, and that's not the case. A defining feature of Bubble Sort is that it only ever compares adjacent elements. The sort presented here is definitely not Bubble Sort.
- JohnHaugeland 5y ago
  I wish you would read the rest of the comment. I clearly explain this.
  - ColinWright 5y ago
    I did. Really, I did. I just happen to disagree with you. Now, it might be that you have more information than I have, and that would be interesting, but based on what you've said, I still think the algorithm presented here is genuinely not Bubble Sort. You said: > the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm. Perhaps I should have emphasised the "is", and said: >> A defining feature of Bubble Sort is that it only ever compares adjacent elements. That might have served to emphasise that I had read your comment and was explicitly disagreeing with you. You claim otherwise ... perhaps I should have asked for an explicit reference from you to support your position, and provided for you the Wikipedia code to support mine. In particular, on Wikipedia it says: procedure bubbleSort(A : list of sortable items) n := length(A) repeat swapped := false for i := 1 to n-1 inclusive do /* if this pair is out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap(A[i-1], A[i]) swapped := true end if end for until not swapped end procedure So taking this as the definition, it explicitly only ever compares adjacent elements of the array. And that's what I said. It might be that it has derived from a version that does more comparisons, and I'd be interested to see evidence for that, but this seems to be the definition of what we call Bubble Sort. More, the algorithm in the linked paper appears at first glance to have the comparison the wrong way round. That's really different from the Bubble Sort that I know. It also explicitly performs n^2 comparisons, and Bubble Sort performs n-1 on each pass, and when it runs the full length every time, it performs (n-1)^2 comparisons at most. It really feels very different.

recursive 5y ago

Bubble sort will not make any changes to a sorted array. It's a similar number of comparisons. They're just different ones.

JohnHaugeland 5y ago
It's a radically different number of comparisons Bubble sort scans the full array repeatedly until finished, but only along the pairwise edge, and usually finishes way early So in an array of 20 elements you have a maximum of 380 comparisons This searches Euler's Little Triangle the whole way every time, so in an array of 20 elements, you have a maximum of 380 comparisons again Seems similar, right? Except doing pairwise you're likely to exit without doing all 19 scans - at the logarithm if it's well distributed - so it probably does either 4 or 5 scans, saving ~80% of the work The issue isn't the ceiling; it's the common floor Doing it the seemingly-normal way radically changes the common floor
- recursive 5y ago
  Thank you for making my point. So not only does this do different comparisons, it "radically" changes the number of "common floor" work. And by the way, there's something wrong with your analysis of the number of scans needed for the 20 element bubble sort. I don't understand your argument, but I did some experiments with a randomly distributed array. I never saw it sort in fewer than 12 scans, after a few dozen trials.

ColinWright 5y ago

> Bubble sort is the comparison of every pair. I'm not sure what you mean here, but it seems like you're saying that bubble sort has every pair compared with every other pair, and that's not the case. A defining feature of Bubble Sort is that it only ever compares adjacent elements. The sort presented here is definitely not Bubble Sort.

JohnHaugeland 5y ago
I wish you would read the rest of the comment. I clearly explain this.
- ColinWright 5y ago
  I did. Really, I did. I just happen to disagree with you. Now, it might be that you have more information than I have, and that would be interesting, but based on what you've said, I still think the algorithm presented here is genuinely not Bubble Sort. You said: > the elimination is so common that many people don't know about it anymore, and think it's a defining part of the algorithm. Perhaps I should have emphasised the "is", and said: >> A defining feature of Bubble Sort is that it only ever compares adjacent elements. That might have served to emphasise that I had read your comment and was explicitly disagreeing with you. You claim otherwise ... perhaps I should have asked for an explicit reference from you to support your position, and provided for you the Wikipedia code to support mine. In particular, on Wikipedia it says: procedure bubbleSort(A : list of sortable items) n := length(A) repeat swapped := false for i := 1 to n-1 inclusive do /* if this pair is out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap(A[i-1], A[i]) swapped := true end if end for until not swapped end procedure So taking this as the definition, it explicitly only ever compares adjacent elements of the array. And that's what I said. It might be that it has derived from a version that does more comparisons, and I'd be interested to see evidence for that, but this seems to be the definition of what we call Bubble Sort. More, the algorithm in the linked paper appears at first glance to have the comparison the wrong way round. That's really different from the Bubble Sort that I know. It also explicitly performs n^2 comparisons, and Bubble Sort performs n-1 on each pass, and when it runs the full length every time, it performs (n-1)^2 comparisons at most. It really feels very different.