4 ms·

Can you clarify what you mean here? I would argue that any decent programmer could hack out a sorting routine, without having the code memorized. If you canno

Can you clarify what you mean here? I would argue that any decent programmer could hack out a sorting routine, without having the code memorized. If you cannot write a binary search routine from scratch, how can you be expected to solve much bigger problems?

kragen 5y ago
Sure, but there are a lot of subtle issues in both sorting and binary search. The simplest sorting routine is probably dumbsort: void dumbsort(int *p, int n) { for (int tmp, 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; } } But it lives up to its name; I can't imagine any reason you should ever use this algorithm. It compiles to 16 instructions but it's O(N³). Insertion sort is more complicated—it compiles to 17 instructions—and is actually a reasonable thing to use in some circumstances: void isort(int *a, size_t n) { for (size_t i = 1; i < n; i++) { for (size_t j = i; j > 0; j--) { if (a[j-1] <= a[j]) break; int tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } That's because it has the lowest constant factor of all the O(N²) comparison sorts on common machines, so it's the absolute fastest way to sort small arrays. (On my laptop it sorts N items in 0.34 ns × N² ± 2%.) And it's also very fast for large arrays of nearly-sorted data, so it's a reasonable way to finish up after a rough quicksort. It took me about five minutes to write that, and it worked the first time I tested it. But that's in part because I find sort routines fascinating and I've been studying them, and programming in C, for almost 30 years. Even if it took you an hour or four hours and required a lot of debugging, you still might be a decent programmer. Especially for jobs where things are less well defined and you have to do a lot of debugging anyway! (By contrast, I've actually spent most of the last hour trying to write a properly working quicksort, the variant that finishes up with a single call to insertion sort, using both notes and a compiler. Of course it produces correct results because of the final insertion sort but it's not as efficient as it should be and I can't figure out why. Apparently I can't brain today... good thing I'm not in a job interview!)

kragen 5y ago

Sure, but there are a lot of subtle issues in both sorting and binary search. The simplest sorting routine is probably dumbsort: void dumbsort(int *p, int n) { for (int tmp, 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; } } But it lives up to its name; I can't imagine any reason you should ever use this algorithm. It compiles to 16 instructions but it's O(N³). Insertion sort is more complicated—it compiles to 17 instructions—and is actually a reasonable thing to use in some circumstances: void isort(int *a, size_t n) { for (size_t i = 1; i < n; i++) { for (size_t j = i; j > 0; j--) { if (a[j-1] <= a[j]) break; int tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } That's because it has the lowest constant factor of all the O(N²) comparison sorts on common machines, so it's the absolute fastest way to sort small arrays. (On my laptop it sorts N items in 0.34 ns × N² ± 2%.) And it's also very fast for large arrays of nearly-sorted data, so it's a reasonable way to finish up after a rough quicksort. It took me about five minutes to write that, and it worked the first time I tested it. But that's in part because I find sort routines fascinating and I've been studying them, and programming in C, for almost 30 years. Even if it took you an hour or four hours and required a lot of debugging, you still might be a decent programmer. Especially for jobs where things are less well defined and you have to do a lot of debugging anyway! (By contrast, I've actually spent most of the last hour trying to write a properly working quicksort, the variant that finishes up with a single call to insertion sort, using both notes and a compiler. Of course it produces correct results because of the final insertion sort but it's not as efficient as it should be and I can't figure out why. Apparently I can't brain today... good thing I'm not in a job interview!)