logoalt Hacker News

enjoyyourlife • last Friday at 10:57 PM • 9 replies • view on HN

Is this just bubble sort?


Replies

azertify • today at 10:02 AM

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

Arainach • today at 10:06 AM

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.

➕ show 1 reply
Muhammad523 • last Saturday at 8:30 PM

No, it's not. There's a science paper with 3 theorems that prove it actually does sort

➕ show 1 reply
throwawayffffas • today at 10:38 AM

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.

rcxdude • today at 10:01 AM

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.

amelius • today at 10:22 AM

The hint is in the "<" operator.

stavros • today at 10:09 AM

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.

Jyaif • today at 10:02 AM

it's bubble sort without the early return.

[edit: my bad, it's not bubble sort]

➕ show 1 reply