“There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.”*
I'm pretty impressed by both Grok's and Gemini's static analysis of it. (I changed the name of the function to algo and asked them to figure out if it's supposed to be a sort algorithm or a search algorithm. Both got it right.)[1] If someone else could please check the same prompt on ChatGPT and Claude (which I don't have) please link.
It's not, but it's conceptually very similar at first glance.
One important thing to note is that bubble sort places one element in the correct position each pass and then *stops looking at that position ever again*.
This algorithm looks at all N elements every pass.
Others have shared a bunch of great videos and writeups. Without reading them, my initial assumption is that this builds things bottom up (such that after the first pass, the element in position 0 is guaranteed to be the lowest element) and that despite it being compared again and again, it's essentially placing one element each pass, but I could be wrong.
Look at it more carefully. Just reading the code, you'd think someone got confused between insertion sort and bubble sort and made a mashup that can't possibly work. But it still does.
It took me a while, but the surprising part is that the inner loop goes back to the first element again, unlike bubble sort which never revisits the outer loop's elements. So, at some point you'll compare element 3 with element 1, and swap so that 3 is smaller than 1, which is surprising.
Paper about this with proof of how/why it works: https://arxiv.org/pdf/2110.01111, which says:
“There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs. Its only appeal may be its simplicity, in terms of lines of code and the “symmetry” of the two loops.”*
Previously (2021): https://news.ycombinator.com/item?id=28758106
I'd like to see a formal proof of this.
Not because I don't believe it's true, but because this might be a nice entry into formal proofs.
https://arxiv.org/pdf/2110.01111
I'm pretty impressed by both Grok's and Gemini's static analysis of it. (I changed the name of the function to algo and asked them to figure out if it's supposed to be a sort algorithm or a search algorithm. Both got it right.)[1] If someone else could please check the same prompt on ChatGPT and Claude (which I don't have) please link.
[1]
https://grok.com/share/c2hhcmQtMw_77a3a16f-642c-4ea7-95c7-28...
and
https://share.gemini.google/HADqPiEaeHQ9
Is this just bubble sort?
Matt Parker has an excellent video on this algorithm which should help illustrate why it's absurd (and not bubble sort): https://www.youtube.com/watch?v=ixXOUeBOPJw
It's not, but it's conceptually very similar at first glance.
One important thing to note is that bubble sort places one element in the correct position each pass and then *stops looking at that position ever again*.
This algorithm looks at all N elements every pass.
Others have shared a bunch of great videos and writeups. Without reading them, my initial assumption is that this builds things bottom up (such that after the first pass, the element in position 0 is guaranteed to be the lowest element) and that despite it being compared again and again, it's essentially placing one element each pass, but I could be wrong.
Technically the first pass will ensure that the smallest element ends up at position 0 even if it's looked at more times.
Bubblesort really is a family of "this is something I figured out myself that runs by looping in O(N^2) by moving things to the front/back"
The hint is in the "<" operator.
That was my first instinct as well. But if you look closer you will see, it's actually insertion sort by someone who didn't pay attention in class.
It misses the revelation you can skip already sorted positions when deiciding what goes in the next position.
Btw. Ofcourse it sorts, it's basically insertion sort with extra swaps.
Look at it more carefully. Just reading the code, you'd think someone got confused between insertion sort and bubble sort and made a mashup that can't possibly work. But it still does.
No, it's not. There's a science paper with 3 theorems that prove it actually does sort
Bubble sort can sort
Every other sorting algorithm does, by definition
It took me a while, but the surprising part is that the inner loop goes back to the first element again, unlike bubble sort which never revisits the outer loop's elements. So, at some point you'll compare element 3 with element 1, and swap so that 3 is smaller than 1, which is surprising.
it's bubble sort without the early return.
[edit: my bad, it's not bubble sort]
Pull up the pseudocode for bubble sort and compare it.
indeed, it's not bubble sort