Sunday, May 17, 2009

Assorted sorts

Let 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:

omkarenator said...

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

git repo is down!

Ben Lynn said...

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

Ben Lynn said...

Update: fixed a bug in my gnome sort code.

uki said...

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

Ben Lynn said...

Thanks! Fixed it.

Ben Lynn said...

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

Ben Lynn said...

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.