2
\$\begingroup\$

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 <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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], &err, 10);
    if (errno || n < 2 || n > 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 < 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 < 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 <= 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->tv_sec + (a->tv_nsec / 1000000000.0);
    double bb = b->tv_sec + (b->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 < n; i++) {
        if (data[i - 1] > data[i]) {
            r = 0;
            break;
        }
    }
    return r;
}

int randto(int n) {
    int mx = (RAND_MAX / n) * n;
    int p;
    do p = rand(); while (p >= 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.

  1. Is my bogosort() wrongly implemented?
  2. Is my bogobogosort() wrongly implemented?
  3. Is my shuffle() wrongly implemented? (but it would influence both functions)
  4. Is my randto() wrongly implemented? I believe there's no bias.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ For me it throws sorties.c: In function ‘timedelta’: sorties.c:82:18: error: dereferencing pointer to incomplete type double aa = a->tv_sec + (a->tv_nsec / 1000000000.0); ^ sorties.c:82:31: error: dereferencing pointer to incomplete type double aa = a->tv_sec + (a->tv_nsec / 1000000000.0); ^ sorties.c:83:18: error: dereferencing pointer to incomplete type double bb = b->tv_sec + (b->tv_nsec / 1000000000.0); ^ ... which version of GCC should I run this in? \$\endgroup\$
    – Caridorc
    Jul 21, 2015 at 15:39
  • 1
    \$\begingroup\$ I'm on FreeBSD, using clang 3.4.1. But you can remove the timing code for a completely Standard version of the program. \$\endgroup\$
    – pmg
    Jul 21, 2015 at 16:11
  • \$\begingroup\$ I'm voting to close this question as off-topic because any reasonable definition of "improve" can not be applied to this code which intends only to make the performance as poor as possible. \$\endgroup\$
    – nhgrif
    Jul 21, 2015 at 19:03
  • \$\begingroup\$ I've closed the question because the code doesn't work as intended (you're asking why bogobogosort doesn't work slowly enough). \$\endgroup\$ Jul 21, 2015 at 19:05
  • \$\begingroup\$ There's a better description of the bogobogosort algorithm at dangermouse.net/esoteric/bogobogosort.html -- this does not implement the algorithm described there. \$\endgroup\$
    – mdfst13
    Jul 22, 2015 at 13:52

1 Answer 1

4
\$\begingroup\$

Not bogobogosort

The way you implemented your bogobogosort, it is actually faster than bogosort because of a few reasons:

  1. 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.

  2. 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.
\$\endgroup\$
2
  • \$\begingroup\$ According to the description at Wikipedia, the first part of bogosort is checking for ordered data. If the first N elements are in order a bogosort of those N elements does not do a single shuffle. So if I have 0 1 2 3 4 6 5 and bogobogosort that I go from bogosort from 2 to 5 elements without any shuffling, then shuffle 6 elements (and go back to bogobogosorting 2). \$\endgroup\$
    – pmg
    Jul 22, 2015 at 10:12
  • \$\begingroup\$ @pmg If that is the proper definition of bogobogosort then it turns out to be faster than bogosort (as the OP's program proves). I'm not familiar with the origins of bogobogosort but in order for it to "run until the heat death of the universe" as claimed, it should look more like the sort I wrote. \$\endgroup\$
    – JS1
    Jul 22, 2015 at 17:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.