No, bubble sort uses a single index to compare items that are next to each other, and also has the condition reversed (> vs <), which is part of the surprise that this sort still has the correct increasing order.
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.
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.
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.
"Bubble sort is a sorting algorithm that works by repeatedly stepping through lists that need to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order." -- https://www.techopedia.com/definition/3757/bubble-sort
I'm really baffled by your claim. I've never seen anything other than the definition or implementation saying that it's adjacent elements being compared. Everywhere I've ever seen it's been a defining feature of the algorithm definition ... yet you claim otherwise.
Can you provide any explicit reference where the Bubble Sort is not explicitly comparing adjacent elements?
This is boring. I'm sorry you're unable to read my first comment, and keep requesting reference you've already recieved.
Notably, you're even providing scans from the TAoCP page I gave you, which have the relevant text carefully trimmed away, and are showing individual paragraphs whose text does not attempt to give a definition, despite that a definition is present on those pages
Who are you trying to convince, Frank? Nobody's reading this thread this late. Did you think I just didn't know what else was on the pages I gave you?
When an anti-vaxxer wants to make a point, they have to turn to hilariously inappropriate sources to pretend they're defended.
Techopedia, tutorials point, BBC news, a 2008 tutorial written by a student, and a random set of tutorials on a page full of broken links and misspellings. And very, very carefully edited Knuth.
Amusingly, one of them even explicitly spells out the same thing I did.
I see you're turning to the best in the business. And ignoring the coiner, again.
I read your comment ... you are calling me a liar, and I don't appreciate that.
I'm providing scans of exactly the part where Knuth says the Bubble Sort only compares adjacent locations, just as I said.
You said:
> Bubble sort is the comparison of every pair.
This is contradicted by the scans of TAoCP that I've provided.
You said:
> If you compare only adjacent pairs, you eliminate an enormous number of redundant comparisons.
That's true, but you are eliminating redundant comparisons from something that is not a Bubble Sort.
> This is bubble sort without the redundancy elimination.
This is contradicted by the scanned excerpts from TAoCP.
> 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.
The comparisons between locations that are not adjacent was never part of the Bubble Sort. You continue to claim otherwise, I have checked your references, as far as I can see they don't support your assertion. Please provide scans to support your claim.
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
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.
