Is this the simplest sorting algorithm?

https://twitter.com/chordbug/status/1523016806348304385

by emadabdulrahim • 4 years ago

10 10 4 years ago

twitter.com

scarface742• 4 years ago

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

cable2600• 4 years ago

Bubble sort is slow.

scarface742• 4 years ago

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

st0le• 4 years ago

Did you see the inequality sign?

cato_the_elder2• 4 years ago

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.

twisteriffic• 4 years ago

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.

cato_the_elder2• 4 years ago

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.

necovek• 4 years ago

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".

fargle• 4 years ago

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

LEDThereBeLight• 4 years ago

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

Is this the simplest sorting algorithm?

Related Stories