4 ms·

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 bas

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.

JohnHaugeland 5y ago
My original comment covers all of this. . > So taking this as the definition Random wikipedia code isn't a definition. Have a nice day
- ColinWright 5y ago
  > Random wikipedia code isn't a definition. Let's look at a few other sites: "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 https://www.techopedia.com/definition/3757/bubble-sort "Bubble ... compares number X to the adjacent number Y." -- https://airfocus.com/glossary/what-is-bubble-sort/ https://airfocus.com/glossary/what-is-bubble-sort/ "Bubble Sort ... works by repeatedly swapping the adjacent elements ..." -- https://www.geeksforgeeks.org/bubble-sort/ https://www.geeksforgeeks.org/bubble-sort/ "... bubble sort works by comparing adjacent pairs of objects in the array." -- http://pkirs.utep.edu/cis3355/Tutorials/chapter9/tutorial9A/bubblesort.htm http://pkirs.utep.edu/cis3355/Tutorials/chapter9/tutorial9A/... "Bubble sort ... each pair of adjacent elements is compared and the elements are swapped if they are not in order." -- https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm https://www.tutorialspoint.com/data_structures_algorithms/bu... "Bubble sort ... Compare the current number with the next number." -- https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/5 https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/5 "Bubble sort ... compares two adjacent elements and swaps them until they are not in the intended order." -- https://www.programiz.com/dsa/bubble-sort https://www.programiz.com/dsa/bubble-sort ======== Added in edit: Scans from TAoCP, Volume 3: https://www.solipsys.co.uk/images/BubbleSort_a.png https://www.solipsys.co.uk/images/BubbleSort_a.png https://www.solipsys.co.uk/images/BubbleSort_b.png https://www.solipsys.co.uk/images/BubbleSort_b.png ======== 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?
  - JohnHaugeland 5y ago
    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. Good luck to you.
    - ColinWright 5y ago
      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. Otherwise I bid you good day, and good health.

JohnHaugeland 5y ago

My original comment covers all of this. . > So taking this as the definition Random wikipedia code isn't a definition. Have a nice day

ColinWright 5y ago
> Random wikipedia code isn't a definition. Let's look at a few other sites: "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 https://www.techopedia.com/definition/3757/bubble-sort "Bubble ... compares number X to the adjacent number Y." -- https://airfocus.com/glossary/what-is-bubble-sort/ https://airfocus.com/glossary/what-is-bubble-sort/ "Bubble Sort ... works by repeatedly swapping the adjacent elements ..." -- https://www.geeksforgeeks.org/bubble-sort/ https://www.geeksforgeeks.org/bubble-sort/ "... bubble sort works by comparing adjacent pairs of objects in the array." -- http://pkirs.utep.edu/cis3355/Tutorials/chapter9/tutorial9A/bubblesort.htm http://pkirs.utep.edu/cis3355/Tutorials/chapter9/tutorial9A/... "Bubble sort ... each pair of adjacent elements is compared and the elements are swapped if they are not in order." -- https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm https://www.tutorialspoint.com/data_structures_algorithms/bu... "Bubble sort ... Compare the current number with the next number." -- https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/5 https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/5 "Bubble sort ... compares two adjacent elements and swaps them until they are not in the intended order." -- https://www.programiz.com/dsa/bubble-sort https://www.programiz.com/dsa/bubble-sort ======== Added in edit: Scans from TAoCP, Volume 3: https://www.solipsys.co.uk/images/BubbleSort_a.png https://www.solipsys.co.uk/images/BubbleSort_a.png https://www.solipsys.co.uk/images/BubbleSort_b.png https://www.solipsys.co.uk/images/BubbleSort_b.png ======== 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?
- JohnHaugeland 5y ago
  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. Good luck to you.
  - ColinWright 5y ago
    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. Otherwise I bid you good day, and good health.