3 ms·

BubbleSort 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 occa

by codr7 2y ago

BubbleSort 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 ago
I wonder what are these occasional situations where you need a quick and dirty sort?
- gus_massa 2y ago
  I 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 ago
  There 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 ago
The 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 ago
I’ve heard of quicksort, but what is dirtysort? :-)

by codr7 2y ago

lpapez 2y ago

I wonder what are these occasional situations where you need a quick and dirty sort?

gus_massa 2y ago
I 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 ago
There 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 ago

The 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 ago

I’ve heard of quicksort, but what is dirtysort? :-)