3 ms·
The algorithm from the paper is indeed an astonishingly simple sorting algorithm, and it is indeed surprising that it works: void cantbelievesort(int *
by kragen 5y ago
The algorithm from the paper is indeed an astonishingly simple sorting algorithm, and it is indeed surprising that it works:
void
cantbelievesort(int *p, size_t n)
{
int tmp;
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < n; j++) {
if (p[i] < p[j]) tmp = p[i], p[i] = p[j], p[j] = tmp;
}
}
}
That's 10 lines of code according to David A. Wheeler's 'SLOCCount,' though arguably 9 would be fairer. Its cyclomatic complexity is 3, with a deepest statement nesting level of 4, and it has 5 variables: three locals plus two arguments. It compiles to these 17 amd64 instructions, occupying 44 bytes of code, although I could probably shave off a third of that if I wrote it by hand:
4007cc: 31 c0 xor %eax,%eax
4007ce: eb 22 jmp 4007f2 <cantbelievesort+0x26>
4007d0: 8b 0c 87 mov (%rdi,%rax,4),%ecx
4007d3: 44 8b 04 97 mov (%rdi,%rdx,4),%r8d
4007d7: 44 39 c1 cmp %r8d,%ecx
4007da: 7d 07 jge 4007e3 <cantbelievesort+0x17>
4007dc: 44 89 04 87 mov %r8d,(%rdi,%rax,4)
4007e0: 89 0c 97 mov %ecx,(%rdi,%rdx,4)
4007e3: 48 ff c2 inc %rdx
4007e6: eb 02 jmp 4007ea <cantbelievesort+0x1e>
4007e8: 31 d2 xor %edx,%edx
4007ea: 48 39 f2 cmp %rsi,%rdx
4007ed: 75 e1 jne 4007d0 <cantbelievesort+0x4>
4007ef: 48 ff c0 inc %rax
4007f2: 48 39 f0 cmp %rsi,%rax
4007f5: 75 f1 jne 4007e8 <cantbelievesort+0x1c>
4007f7: c3 retq
However, arguably, this sort routine is even simpler. It may or may not be surprising that it works:
void
dumbsort(int *p, size_t n)
{
int tmp;
for (size_t i = 1; i < n; i++) {
if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0;
}
}
By the same metric, that's only 8 lines of code (also only 8 by my "fairer" metric), its cyclomatic complexity is only 2, its deepest statement nesting level is only 3, and it has only 4 variables (the same two arguments, but two locals instead of three). It compiles to only 15 amd64 instructions, occupying only 43 bytes:
4007f8: b8 01 00 00 00 mov $0x1,%eax
4007fd: eb 1e jmp 40081d <dumbsort+0x25>
4007ff: 4c 8d 04 87 lea (%rdi,%rax,4),%r8
400803: 48 8d 54 87 fc lea -0x4(%rdi,%rax,4),%rdx
400808: 41 8b 08 mov (%r8),%ecx
40080b: 44 8b 0a mov (%rdx),%r9d
40080e: 44 39 c9 cmp %r9d,%ecx
400811: 7d 07 jge 40081a <dumbsort+0x22>
400813: 45 89 08 mov %r9d,(%r8)
400816: 31 c0 xor %eax,%eax
400818: 89 0a mov %ecx,(%rdx)
40081a: 48 ff c0 inc %rax
40081d: 48 39 f0 cmp %rsi,%rax
400820: 72 dd jb 4007ff <dumbsort+0x7>
400822: c3 retq
On every complexity metric that was ready to hand, dumbsort is simpler than cantbelievesort. Except computational complexity: dumbsort is O(N³) while cantbelievesort is only O(N²).
Dumbsort is similar to gnome sort, but arguably somewhat simpler: whenever it finds an out-of-order pair, after reversing it, it throws up its hands and starts over (i = 0, xor %eax, %eax).
I don't think I invented it, but I can't remember who did. I'd be grateful for pointers.
- Dylan16807 5y agoFun algorithm! But I think translating to C and counting lines of code ends up overestimating the complexity of looping from 1 to n. And using a temporary to swap is definitely overestimating the complexity, though that doesn't affect the comparison. If we treat looping up to n as one line of code, then both algorithms have the same count. And I think it's pretty fair to do that. Fortran, BASIC, APL, Perl, and so many others have syntax that's basically "for i = x to y". Let alone mathy languages that can loop over an array with a single character. Honestly, C is kind of weird for not having syntax for that. For cyclomatic complexity, I don't know, setting i to 0 seems like cheating. You definitely win on variable use. Separate from the analysis, I have to wonder if there's a clever way to work in a saturating i-=2 instead of i=0. Then you can have N² efficiency without really changing the complexity.
- kragen 5y agoAny measurement of "code complexity" is relative to some particular computational basis; which one do we choose? In APL sorting the array P in ascending order is just P[⍋P] which result you can optionally assign back to P by prepending "P←". So, by the APL measure, none of these algorithms is "as simple as" invoking the builtin sort operator. (Which is probably also faster.) APL doesn't actually have any 'syntax that's basically "for i = x to y".' If we take Perl golf as our measure of "code complexity" you can't use a for-loop for dumbsort, because zeroing the ostensible loop counter doesn't reset the loop; there's a hidden loop counter you can't alter. You have to use an explicit while loop, which makes the cantbelievesort much simpler. Smalltalk and Python are the same way. But of course the shortest way to sort in all three languages is to invoke the built-in sort function: sort @p, p asSortedCollection, p.sort(). (You're right about FORTRAN and BASIC, though. You can futz with loop counters in those languages, just like in C.) That's why I chose C and machine code as my metric. Smalltalk and Python maintain this hidden loop counter in the implementation, and also do garbage collection behind the scenes (which you might think was irrelevant, but the write barrier can significantly slow down heavily mutating algorithms like this one) and bounds checking. Numpy and APL additionally do implicit array broadcasting. All of these languages (except FORTRAN and BASIC) have built-in sort routines that are simpler to invoke than writing your own sort function. So I was looking for the language that would keep me as honest as possible. But of course in a different machine language the answer might be different. For example, I haven't seen an instruction set with dedicated looping instructions that support nested loops, but make it inconvenient to clobber the loop counter in the middle of the loop, but it would be easy to design one, and there might be some advantage to doing so. (Code density, maybe, or unrolling iterations of the loop into a pipeline.) Then dumbsort would lose, because as in Python, it would have to be written as a regular while loop, which usually costs four instructions: an increment, a compare, a conditional jump, and an unconditional jump. I think the i-=2 tweak you suggest converts dumbsort into gnomesort, which is just a sort of pessimized insertion sort. As your "saturating" comment suggests, gnomesort needs an additional operation to avoid running off the beginning of the array; some instruction sets do provide saturating arithmetic (it's often useful for DSP and graphics, even if it's not as often useful for indexing arrays), and many others provide a binary "max" operation (SSE's PMAXSW and friends, as well as, say, APL ⌈) which could convert an ordinary subtraction into a saturating subtraction.