Is this the simplest sorting algorithm?

twitter.com

10 points·emadabdulrahim··10 comments

The fact that something is short does not mean it's "simple". Simple is something that's easy to understand.

And while it's pretty clear that one could explain this in simpler terms, it's never going to be "simple" because it relies on a side effect and direction of (what may seem to be) the core logic (in iteration i, put the largest number at A[i]).

So no, this ain't the "simplest sorting algorithm".

I must be the only one who thinks this is actually pretty interesting.

That’s just a bubble sort. I learned that in elementary school in the 80s.

Bubble sort is slow.

I realize that. But tweet was acting like it was “One Weird Trick” that was a new discovery.

Did you see the inequality sign?

No, it's not. But that's kinda the point. This is mildly interesting because at the first glance it kinda looks like a wrongly implemented bubble sort, but it actually works.

It's a slightly modified selection sort. Bubble compares arr[j] to arr[j+1]. Selection sort normally compares arr[j] to arr[indexofsmallest]. The algorithm here avoids the need to track smallest index by just swapping the next smallest value found to a known location, arr[i]. Trades a single pointer worth of memory for n^2 swaps.

I think it's more similar to insertion sort. In the first iteration of the outer loop, it moves the maximum to A[1]. After that, it works essentially like insertion sort, except that it does a bunch of unnecessary comparisons after finding the location to insert the element, and does the shifting in a slightly weird way.

post the source, not the twit about it: https://arxiv.org/pdf/2110.01111.pdf

Reply on news.ycombinator.com