4 ms·
Why is this algorithm at all surprising? (I'm really not trying to brag - I assume I must be missing something, that I'm naïve to think it obviously works, and
by OJFord 4y ago
Why is this algorithm at all surprising?
(I'm really not trying to brag - I assume I must be missing something, that I'm naïve to think it obviously works, and it actually works for a different reason.)
In plain English - 'for every element, compare to every element, and swap position if necessary' - .. of course that works? It's as brute force as you can get?
- Asooka 4y agoThe comparison is not the way you'd expect. Index j goes past index i, but the comparison doesn't change. What you propose is a condition more like if ((a[i] < a[j]) != (i < j)) swap(a, i, j) ; Which obviously works. The surprising algorithm sorts even though it swaps elements that are already ordered.
- OJFord 4y agoOk, I think I see why it's a bit weird '1,2,3 when i=1 and j=3 it swaps them anyway' sort of thing? But i-loop comes through 'afterwards', so when i=3 (value now 1) and j=1 (3) it sets them straight. It still seems quite intuitive, but I think I cheated by skimming over it initially and thinking it was clear, whereas actually I've thought about it more now. (Not to compare myself to anything like him, I'm no mathematician at all, but I'm reminded of an amusing Erdós anecdote in which he apparently paused mid-sentence in some lecture, left the room, and came back some time later continuing 'is clearly [...]' or similar!)
- YetAnotherNick 4y agoIf the second loop is from j = i to n, it is easy to see that it will sort in decreasing order. But notice j = 1 to n, then suddenly it will sort in increasing order
- shp0ngle 4y agolook again at the comparison direction. It is opposite! It works but not as you think it does.