`void x(int *p, int *q)`be function that swaps its arguments, namely, after execution,

`*p`is equal to the original value of

`*q`and vice versa.

What do the following functions do?

void f(int *m, int *n) { int *p; for(p = m; p < n; p -= *p > p[1] ? x(p, p + 1), p != m : -1); } void f(int *m, int *n) { int *p, *q; for(p = m; p <= n; p++) for(q = p; q <= n; *p > *q ? x(p, q) : 0, q++); } void f(int *m, int *n) { int i, j, k; for(i = 1; (k = i) <= n - m; i++) while(k && m[j = k - 1 >> 1] < m[k]) x(m + j, m + k), k = j; for(k--; x(m, m + k--), k;) for(i = 0; j = 2 * i + 1, k >= (j += k > j && m[j] <= m[j + 1]) && m[j] > m[i]; x(m + j, m + i), i = j); } void f(int *m, int *n) { int *p, *q, i; do for (i = 0, p = q = m, ++q; q <= n; p = q++) *p > *q ? x(p, q), i = 1 : 0; while(i); } void f(int *m, int *n) { int *p, *q; for(p = m + 1, q = n; p < q; *p > *m ? x(p, q--) : *p++); m != n ? *m > *p ? x(m, p) : 0, f(m, --p), f(q, n) : 0; } void f(int *m, int *n) { int *p, *q, i, j; for(p = m + 1; p <= n; p++, *q = i) for(i = *p, q = p; q > m && i < (j = *(q - 1)); *q-- = j); } void f(int *m, int *n) { static short s[] = { 1, 4, 10, 23, 57, 132, 301, 701, 1750 }; int *p, *q, i, j, a, b; for(a = sizeof(s)/sizeof(short) - 1; a && s[a] > n - m; a--); while(a >= 0) for(p = m + (b = s[a--]); p <= n; p++, *q = i) for(i = *p, q = p; q > m && i < (j = *(q - b)); *q = j, q -= b); }

The title is a big hint, but if you're still not sure, experiment with a function by compiling it with the following code, and supply some integers on standard input.

#include <stdio.h> void f(int *m, int *n); void x(int *p, int *q) { int i = *p; *p = *q, *q = i; } int main() { enum { limit = 8192 }; int a[limit], *n, *k; for(n = a; 1 == scanf("%d", n) && n - a < limit; n++); puts("in:"); for (k = a; k < n; k++) printf(" %d", *k); puts(""); f(a, n - 1); puts("out:"); for (k = a; k < n; k++) printf(" %d", *k); puts(""); return 0; }

Can you identify each algorithm? The answers are, in some order, bubble sort, gnome sort, insertion sort, selection sort, shell sort, heapsort and quicksort.

The real puzzle is why I bothered. All I can say is you don't have to be a chef to enjoy making spaghetti: see the International Obfuscated C Code Contest.

## 7 comments:

http://cs.stanford.edu/~blynn/sort.git

git repo is down!

I forgot to update that page. It's now http://cs.stanford.edu/~blynn/scrap/sort.git.

Update: fixed a bug in my gnome sort code.

the first function, I think there is one lonely parenthness out there.

Thanks! Fixed it.

Looking at it again, I just realized I could eliminate a few characters and a variable, so I rewrote it.

Whoa! I also spotted a bug in heapsort (now fixed). It was sorting the array, but because I incorrectly reused a variable in an inner loop, it wasn't necessarily running in O(n log n) time.

Post a Comment