4 ms·
Is this the simplest sorting algorithm?
- LEDThereBeLight 4y agoI must be the only one who thinks this is actually pretty interesting.
- scarface74 4y agoThat’s just a bubble sort. I learned that in elementary school in the 80s.
- cable2600 4y agoBubble sort is slow.
- scarface74 4y agoI realize that. But tweet was acting like it was “One Weird Trick” that was a new discovery.
- st0le 4y agoDid you see the inequality sign?
- cato_the_elder 4y agoNo, 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 4y agoIt'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_elder 4y agoI 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 4y agoThe 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 4y agopost the source, not the twit about it: https://arxiv.org/pdf/2110.01111.pdf https://arxiv.org/pdf/2110.01111.pdf