5 ms·
Formatted: For easier exposition in the proof later on, the array is 1-based, so the elements are A[1]...A[n]. Algorithm 1 ICan’tBelieveItCanSort(A[1
by ColinWright 2y ago
Formatted:
For easier exposition in the proof later on, the array is 1-based, so the elements are A[1]...A[n].
Algorithm 1
ICan’tBelieveItCanSort(A[1..n])
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]
- AnimalMuppet 2y agoIsn't that just BubbleSort? And, if so: they're writing Arxiv papers on BubbleSort now?
- sorokod 2y agoNote the: A[i] < A[j]
- casey2 2y agoYou can use 1..n+1 for both indices to get a sorted array with >
- skeaker 2y agoNo.
- GuB-42 2y agoIt is not, it is actually closer to an insertion sort. The interesting part is that it often comes up when the one writing the algorithm doesn't know what he is doing, and yet, it works. It may look like a BubbleSort because it is a common wrong implementation of BubbleSort. EDIT: insertion, not selection
- capitainenemo 2y agoYeah, section 3.2 of the PDF, titled '"Improving" the algorithm' notes that they have "rediscovered" insertion sort by simply adjusting the loop indices. (they also document a variant in 3.1 with similar indices tweaking which they describe as similar to an exchange sort)
- deepspace 2y agoYou did not bother to read the article, did you?
- codr7 2y agoBubbleSort keeps going until no more swaps happen, this algorithm specifies up front which items to compare. I actually think it's pretty cool, it happens occasionally that I just need a quick and dirty sort and this is easier to get right.
- lpapez 2y agoI wonder what are these occasional situations where you need a quick and dirty sort?
- gus_massa 2y agoI had to change the order of the rows and columns of a matrix to force the diagonal to be ordered. One possibility was to use the sort function on the diagonal, somehow get the permutation, and then apply the permutation to all the rows and columns. How had can it be? There is a 50% chance of apply the permutation in the wrong direction, and other possible tricky details. Since the worst case was N=20, I used bubble sort that is as quick and dirty, but it's also obvious and well known.
- codr7 2y agoThere are plenty of standard libraries out there that leave a lot to wish for. Sometimes I'm writing my own language, trying to figure something else out and don't feel like being sidetracked. Sometimes predictable performance is more important than optimal. Let's just say there are plenty of reasons why someone might want to do that.
- GuB-42 2y agoThe really unintuitive bit is that the condition is the reverse of what you would expect, so I wouldn't call it "easy to get right". Exchange sort is more intuitive and almost as simple, and if you don't mind something a little less intuitive but still very simple, just do insertion, it is often considered the best of the simple (N^2) sorting algorithms. For me, the most intuitive and the less likely I would get wrong would be selection. It is actually the one I came up with naturally before I even knew about sorting algorithms, it is a couple of lines longer than the others though, and often considered worse than insertion.
- kccqzy 2y agoBubble sort only swaps adjacent elements—that's why it's called bubble. This doesn't.
- tasty_freeze 2y agoThis isn't surprising to me in the least that it works. In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it. In the second pass (i=2), A[2] will end up with the 2nd largest value (which might be the same as the largest value, if it appeared more than once in the list). And so on.
- ColinWright 2y agoYou would appear to be wrong, because A[1] ends up with the smallest element. Specifically, on each case when i=2 and higher, j will still start at 1, so A[1] will still get referenced.
- jmholla 2y agoOn the first pass, A[1] ends up the largest element. On subsequent passes, it ends up with the smallest element in A[1:i].
- bmacho 2y ago> In the first pass (i=1), A[1] will end up with the largest value and a later pass cannot displace it. Nah, it will get displaced later. Notice that in the inner loop j goes from 1, and not from i. After i=1 A[1] will be the largest element, but after the next big step, after i=2, A[2] will be the largest element. (And after i=n, A[n] will be the largest element, as expected.) > In the second pass (i=2), A[2] will end up with the 2nd largest value The algorithm sorts the array ascending, and not descending. There is an example run linked in a grandkid comment, by jmholla. (This comment was entirely rewritten.)