bogosort.c --- a joke program written seriously

This is a kind of bogosort. It surely succeed unless malloc() returns NULL. It is a stable sort.

The idea: We try to sort a[ ] of size N. Let c[ ] be a permutation of {0, 1, ..., N-1}. There exists at least one permutation such that a[c[i]] is sorted.

a prototype

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define VERBOSE

#define N 4     /* the size of the array to be sorted */

int a[N];       /* the array to be sorted */
int c[N];       /* a permutation of 0, 1, 2, ..., N-1 */

void init(void);
int issorted(void);
int next(void);
void swap(int i, int j);
void sort(void);

int main() {
  int i;

  srand((unsigned)time(NULL));  /* initialize a[ ] by rand() */
  printf("-- before --\n");
  for (i = 0; i < N; i++) {
    a[i] = rand() % 9 + 1;
    printf(" %2d", a[i]);
  }
  putchar('\n');

  for (init(); issorted() != 1; next()) { /* main loop */
    ;
  }

  sort();
  printf("-- after --\n");
  for (i = 0; i < N; i++) {
    printf(" %2d", a[i]);
  }
  putchar('\n');
}


/* initialize c[ ] by 0, 1, 2, ..., N-1 */
void init(void) {
  int i;

  for (i = 0; i < N; i++) {
    c[i] = i;
  }
}


/* if a[c[i]] <= a[c[i+1]] for every i, returns 1, else 0 */
int issorted(void) {
  int i;

#ifdef VERBOSE
  for (i = 0; i < N; i++) { 
    printf("%x", c[i]);
  }
  for (i = 0; i < N; i++) {
    printf(" %2d", a[c[i]]);
  }
  putchar('\n');
#endif
  for (i = 0; i < N-1 && a[c[i]] <= a[c[i+1]]; i++) {
    ;
  }
  return i == N-1 ? 1 : 0;
}  


/* changes c[ ] to the next permutation in the lexicographic order.     */
/* return value: 1 ... success, 0 ... failure (if no next permutation). */
/*                                                                      */
/* example: assume that c[ ] is "035421".  Note that 3 < 5 > 4 > 2 > 1. */
/* (We use the notation in mathematics, not in C.)  First, search for 3.*/
/* Then, search for 4.  Exchanging them, we have "0345321".  Revease    */
/* "5321" to "1235".  Then, we have "041235".  This is the next         */
/* permutation.                                                         */
int next(void) {
  int i, j;

  for (i = N-1; i > 0 && c[i-1] > c[i]; i--) {  /* search for 3 */
    ;
  }
  if (i == 0) {
    return 0;
  }
  for (j = i; j < N && c[j] > c[i-1]; j++) {    /* search for 4 */
    ;
  }
  swap(i-1, j-1);                               /* exchange 3 and 4 */
  for (j = N-1; i < j; i++, j--) {              /* reverse "5321" to "1235" */
    swap(i, j);
  }
  return 1;
}


void swap(int i, int j) {
  int tmp = c[i];

  c[i] = c[j]; c[j] = tmp;
}


/* sort a[ ] according to c[ ].          */
/* if a[ ] is "6139", then c[ ] is 1203. */
/* a[i] becomes "1369".                  */
void sort(void) {
  const int done = -1;
  int start, i;
  int tmp;

  while (1) {
    for (start = 0; start < N && c[start] == done; start++) {
      ;
    }
    if (start == N) {
      return;
    }

    if (c[start] == start) {
      c[start] = done; continue;
    }

    tmp = a[start]; i = start; 
    while (c[i] != start) {
      int i_prev = i;

      a[i] = a[c[i]];
      i = c[i]; c[i_prev] = done;
    }
    a[i] = tmp; c[i] = done;
  }
}

program files including bogosort.c and bogosort.h

main.c, bogosort.c, and bogosort.h. Compile by "cc main.c bogosort.c".

main.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bogosort.h"

#define N 12            /* the size of the each element of the array to be sorted */

struct object {
  int r;
  double n;             /* there is no reason to use double, instead of int. */
};

struct object a[N];     /* the array to be sorted */

int compare(const void *p, const void *q);

int main(int argc, char *argv[]) {
  int i;
  time_t t0, t1;

  if (argc == 1) {              /* if there is no command line option */
    srand((unsigned)time(NULL));
    for (i = 0; i < N; i++) {
      a[i].r = rand() % 9 + 1;  /* initialize a[ ]  by rand() */
      a[i].n = i;
    }
  } else {                      /* if there is command line options */
    for (i = 0; i < N; i++) {
      a[i].r = N-1-i;           /* initialize a[ ] for the worst case */
      a[i].n = i;
    }
  }
  printf("-- before --\n");
  for (i = 0; i < N; i++) {     /* print a[ ] */
    printf("%2d ", a[i].r);
  }
  putchar('\n');
  for (i = 0; i < N; i++) {
    printf("%2.0f ", a[i].n);
  }
  putchar('\n');

  t0 = time(NULL);
  bogosort(a, N, sizeof(struct object), compare);
  t1 = time(NULL);

  printf("-- after --\n");
  for (i = 0; i < N; i++) {     /* print a[ ] */
    printf("%2d ", a[i].r);
  }
  putchar('\n');
  for (i = 0; i < N; i++) {
    printf("%2.0f ", a[i].n);
  }
  putchar('\n');
  printf("%f sec.\n", difftime(t1, t0));
}

int compare(const void *p, const void *q) {
  return ((struct object *)p)->r - ((struct object *)q)->r;
}

bogosort.c.

#include <stdio.h>
#include <stdlib.h>
#include "bogosort.h"

int *c;         /* the address to the array of a permutation of 0 to N-1 */
int *d;         /* a copy of c[ ] */

static void init(int n);
static int issorted(void *base, size_t n, size_t size, int (*comp)(const void *, const void *));
static int next(int *p, int n);
static void swap(int *p, int i, int j);
static void sort(void *base, size_t n, size_t size);

int bogosort(void *base, size_t n, size_t size, int (*comp)(const void *, const void *)) {
  int i, tmp;

  c = malloc((sizeof(int)) * n);
  if (c == NULL) {              /* not enough memory */
    return 0;                   /* failure */
  }
  d = malloc((sizeof(int)) * n);
  if (d == NULL) {              /* not enough memory */
    free(c); return 0;          /* failure */
  }

  for (init(n); issorted(base, n, size, comp) != 1; next(c, n)) {
    ;
  }

  sort(base, n, size);

  free(d), free(c);

  return 1;                     /* success */
}


/* initialize c[ ] */
static void init(int n) {
  int i;

  for (i = 0; i < n; i++) {
    c[i] = i;
  }
}


static int issorted(void *base, size_t n, size_t size, int (*comp)(const void *, const void *)) {
  int i;

  for (i = 0; i < n-1 && (*comp)((char *)base + c[i] * size, (char *)base + c[i+1] * size) <= 0; i++) {
    ;
  }
  return i == n-1 ? 1 : 0;
}


static int next(int *p, int n) {
  int i, j;

  for (i = n-1; i > 0 && p[i-1] > p[i]; i--) {
    ;
  }
  if (i == 0) {
    return 0;
  }
  for (j = i; j < n && p[j] > p[i-1]; j++) {
    ;
  }
  swap(p, i-1, j-1);
  for (j = n-1; i < j; i++, j--) {
    swap(p, i, j);
  }
  return 1;
}


static void swap(int *p, int i, int j) {
  int tmp = p[i];

  p[i] = p[j]; p[j] = tmp;
}


static void sort(void *base, size_t n, size_t size) {
  const int done = -1;
  int start, j, i;
  char tmp;

  for (j = 0; j < size; j++) {
    for (i = 0; i < n; i++) {
      d[i] = c[i];
    }

    while (1) {
      for (start = 0; start < n && d[start] == done; start++) {
        ;
      }
      if (start == n) {
        break;
      }

      if (d[start] == start) {
        d[start] = done; continue;
      }

      tmp = ((char *)base)[start * size + j]; i = start; 
      while (d[i] != start) {
        int i_prev = i;

        ((char *)base)[i * size + j] = ((char *)base)[d[i] * size + j];
        i = d[i]; d[i_prev] = done;
      }
      ((char *)base)[i * size + j] = tmp; d[i] = done;
    }
  }
}

bogosort.h

int bogosort(void *base, size_t n, size_t size, int (*comp)(const void *, const void *));

/* almost same as qsort().  It returns 1 if secceeded, 0 if failed. */
/* malloc() is used in this funcion.                                */

test result and estimated time

This is an Ο(N*N!) algorithm.

You must be patient to use this program!