News for hackers. Stuff that matters.
Re:Is this the simplest sorting algorithm? by necovek on Sunday May 08, 2022 @12:34AM (#31301334)
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".

Re:Is this the simplest sorting algorithm? by LEDThereBeLight on Thursday May 12, 2022 @10:14AM (#31354524)
I must be the only one who thinks this is actually pretty interesting.
Re:Is this the simplest sorting algorithm? by scarface74 on Saturday May 07, 2022 @10:43PM (#31300759)
That’s just a bubble sort. I learned that in elementary school in the 80s.
Re:Is this the simplest sorting algorithm? by cato_the_elder on Sunday May 08, 2022 @12:14AM (#31301234)
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.
Re:Is this the simplest sorting algorithm? by twisteriffic on Sunday May 08, 2022 @01:10AM (#31301494)
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.
Re:Is this the simplest sorting algorithm? by cato_the_elder on Sunday May 08, 2022 @01:27AM (#31301594)
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.
Re:Is this the simplest sorting algorithm? by st0le on Saturday May 07, 2022 @11:42PM (#31301072)
Did you see the inequality sign?
Re:Is this the simplest sorting algorithm? by cable2600 on Saturday May 07, 2022 @11:09PM (#31300900)
Bubble sort is slow.
Re:Is this the simplest sorting algorithm? by scarface74 on Saturday May 07, 2022 @11:13PM (#31300923)
I realize that. But tweet was acting like it was “One Weird Trick” that was a new discovery.
Re:Is this the simplest sorting algorithm? by fargle on Sunday May 08, 2022 @01:19PM (#31306021)
post the source, not the twit about it: https://arxiv.org/pdf/2110.01111.pdf