5 ms·
Isn't that just BubbleSort? And, if so: they're writing Arxiv papers on BubbleSort now?
by AnimalMuppet 2y ago
Isn'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.
- beng-nl 2y agoI’ve heard of quicksort, but what is dirtysort? :-)
- kccqzy 2y agoBubble sort only swaps adjacent elements—that's why it's called bubble. This doesn't.