logoalt Hacker News

Arainach • today at 10:06 AM • 1 reply • view on HN

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.


Replies

whizzter • today at 10:18 AM

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"

➕ show 1 reply