Bogosort vs bogobogosort A question on Stack Overflow had me look up the article on bogosort on Wikipedia.

There they describe the bogosort algorithm and the bogobogosort algorithm. They say, about this last algorithm, that:


  bogobogosort was designed not to succeed before the heat death of the universe on any sizable list.


I wrote a program to compare these 2 algorithms and got somewhat conflicting results: bogosort performs worse than bogobogosort for arrays up to 12 elements.

I am more inclined to believe my code is wrong than Wikipedia. Of course it can be that 12 is not a sizable enough list and the difference starts being noticeable with larger arrays.

#include &lt;errno.h&gt;
#include &lt;limits.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;

void quit(const char *msg) __attribute__((noreturn));
void datainit(int *data, size_t n);
void acopy(int *dst, const int *src, size_t n);
unsigned long bogosort(int *data, size_t n);
unsigned long bogobogosort(int *data, size_t n);
double timedelta(const struct timespec *b, const struct timespec *a);
void shuffle(int *data, size_t n);
int sorted(int *data, size_t n);
int randto(int n);

int main(int argc, char **argv) {
    int data[20], data2[20];
    unsigned long n;
    unsigned long s[2];
    struct timespec t[3];
    char *err;

    if (argc != 2) quit("Specify number of elements.");
    errno = 0;
    n = strtoul(argv[1], &amp;err, 10);
    if (errno || n &lt; 2 || n &gt; 20) quit("number between 2 and 20");

    srand((unsigned)time(0));
    datainit(data2, n);

    clock_gettime(CLOCK_MONOTONIC, t + 0);
    acopy(data, data2, n);
    s[0] = bogosort(data, n);
    clock_gettime(CLOCK_MONOTONIC, t + 1);
    acopy(data, data2, n);
    s[1] = bogobogosort(data, n);
    clock_gettime(CLOCK_MONOTONIC, t + 2);

    printf("    bogosort shuffled %12lu cards in %f seconds.\n", s[0], timedelta(t + 1, t + 0));
    printf("bogobogosort shuffled %12lu cards in %f seconds.\n", s[1], timedelta(t + 2, t + 1));

    return 0;
}

void quit(const char *msg) {
    if (msg) fprintf(stderr, "%s\n", msg);
    exit(EXIT_FAILURE);
}

void datainit(int *data, size_t n) {
    for (size_t i = 0; i &lt; n; i++) data[i] = (int)i;
    shuffle(data, n);
}

void acopy(int *dst, const int *src, size_t n) {
    for (size_t i = 0; i &lt; n; i++) dst[i] = src[i];
}

unsigned long bogosort(int *data, size_t n) {
    unsigned long c = 0;
    while (!sorted(data, n)) {
        c += n;
        shuffle(data, n);
    }
    return c;
}

unsigned long bogobogosort(int *data, size_t n) {
    unsigned long c = 0;
    for (size_t b = 2; b &lt;= n; b++) {
        while (!sorted(data, b)) {
            c += b;
            shuffle(data, b);
            b = 2;
        }
    }
    return c;
}

double timedelta(const struct timespec *b, const struct timespec *a) {
    double aa = a-&gt;tv_sec + (a-&gt;tv_nsec / 1000000000.0);
    double bb = b-&gt;tv_sec + (b-&gt;tv_nsec / 1000000000.0);
    return bb - aa;
}

void shuffle(int *data, size_t n) {
    if (n == 1) return;
    int p = randto((int)n);
    int tmp = data[p];
    data[p] = data[n - 1];
    data[n - 1] = tmp;
    shuffle(data, n - 1);
}

int sorted(int *data, size_t n) {
    int r = 1;
    for (size_t i = 1; i &lt; n; i++) {
        if (data[i - 1] &gt; data[i]) {
            r = 0;
            break;
        }
    }
    return r;
}

int randto(int n) {
    int mx = (RAND_MAX / n) * n;
    int p;
    do p = rand(); while (p &gt;= mx);
    return p % n;
}


And this is a possible result for an array with 10 elements


% ./a.out 10
    bogosort shuffled     13816640 cards in 0.400548 seconds.
bogobogosort shuffled      1102233 cards in 0.027740 seconds.


So, unexpectedly bogosort shuffled more cards than bogobogosort and took more time doing it.


Is my bogosort() wrongly implemented?
Is my bogobogosort() wrongly implemented?
Is my shuffle() wrongly implemented? (but it would influence both functions)
Is my randto() wrongly implemented? I believe there's no bias.
Not bogobogosort
The way you implemented your bogobogosort, it is actually faster than bogosort because of a few reasons:

After you successfully bogosort k elements, you immediately check whether k+1 elements are sorted.  This means that if on a previous shuffle, you happened to shuffle m elements all in order, then after you sort the first two elements you will immediately reach m.
For example, suppose you reach 5 cards and then fail.  You shuffle 5 cards and then start over at 2.  If those 5 cards happen to be in sorted order, you will immediately reach 6 as soon as you put the first 2 cards in order.

Because of point #1, your bogobogosort is actually faster than the bogosort because it only needs to sort n-1 cards instead of n.  After it sorts n-1 cards, it checks the order of n cards and may fail.  But in failing, it reshuffles n cards so that each time it sorts n-1 cards it has a 1/n chance of eventually succeeding.  So the total number of cards shuffled is on the order of (n-1) * (n-1)! * n which simplifies to (n-1) * n!, compared to the bogosort which shuffles n * n! cards.
I believe that the same principle applies at each step, so the time is even less than (n-1) * n!.  I'm not sure of the exact math but from running your program it appears that the bogobogosort runs in approximately the same time as the bogosort with one fewer cards.  I.e. Your_bogobogosort(n) = bogosort(n-1).


A proper bogobogosort
I rewrote your bogobogosort function to be like this:
unsigned long bogobogosort(int *data, size_t n) {
    unsigned long c = 0;
    size_t b = 2;

    while (1) {
        if (sorted(data, b)) {
            if (b == n)
                break;
            b++;
        } else {
            b = 2;
        }
        c += b;
        shuffle(data, b);
    }
    return c;
}

The key difference here is that after each success where it increments b, it reshuffles the deck to prevent point #1 above from happening..  With this change, I get output like this:
% ./a.out 6
    bogosort shuffled         1044 cards in 0.000013 seconds.
bogobogosort shuffled     54464568 cards in 0.500339 seconds.