Bogosort - what is this?

Question

What exactly does the bogosort sorting algorithm?

Because many say he’s inefficient?

Answer 1

The bogosort is an algorithm consisting of the following:

O array está ordenado?
  Se sim, então excelente, fim do algoritmo.
  Se não, embaralhe ele aleatoriamente e volte para o começo.

This algorithm is extremely simple, but also extremely inefficient. And it basically consists of shuffling the array as many times as needed until by sheer luck and chance, the random ordering of the elements turns out to be the correct one. Even partially ordered or almost ordered orders are completely and blindly discarded in their entirety and end up helping nothing.

The result is that the larger the array, the greater the amount of lucky that one must have in order for the correct ordering to appear on a whim of chance. Strictly speaking, in the worst case, an infinite number of attempts would be necessary and correct ordering would never arise (which tends to happen if the random generator used to shuffle is addicted in some way). Considering that there are no statistical biases in the random ordering generator, the probability of any randomly generated ordering being correct is (which gives a time complexity of the average case of , where is the number of elements of the array.

How much is , the probability of hit? Well, see the following table:

 n                          n!    Probabilidade
-------------------------------------------------------------
 1                           1    100,00000000%
 2                           2     50,00000000%
 3                           6     16,66666666%
 4                          24      4,16666666%
 5                         120      0,83333333%
 6                         720      0,13888888%
 7                        5040      0,01984126%
 8                       40320      0,00248015%
 9                      362880      0,00027557%
10                     3628800      0,00002755%
15               1307674368000      0,000000000007647%
20         2432902008176640000      0,000000000000000000411%
25  15511210043330985984000000      0,(25 zeros)6447%
30  2,65 * (10^32)                  0,(32 zeros)3699%

That is, the probability of luck and chance choosing the correct ordering worsens very quickly each time an element is added. In fact, the rate of worsening is more than exponential.

How long would that take? Well, let’s assume that your machine is super fast and is able to shuffle and test whether a given array is ordered, 1 billion times per second (which is not so true, because larger arrays tend to take longer to shuffle and test than smaller ones, but to maintain a little bit of optimism, let’s assume that large arrays take the same long to be shuffled and tested than small ones). So how long would it take on average^*?

 n        Tempo
-------------------------------
 1      1 nanosegundo
 2      1 nanosegundo
 3      3 nanosegundos
 4     12 nanosegundos
 5     60 nanosegundos
 6    360 nanosegundos
 7    2,5 microsegundos
 8     20 microsegundos
 9    182 microsegundos
10   1,82 milissegundos
15     10 minutos e 54 segundos
20     38 anos e 7 meses
25  245,7 milhões de anos
30    4,2 quatrilhões de anos

4.2 quadrillion years to order an array of 30 elements even making 1 billion tests per second!? I think it’s clear why the bogosort is an inefficient algorithm!

And to see the scale of inefficiency, just see that to sort 15 elements, it would take on average 10 minutes and 54 seconds (something that any child would do in a few seconds), but just double the number of elements and the time jumps to four years. This is because time growth is worse than exponential in input size. And look we’re using a super machine that can shuffle the array and see if it’s ordered a billion times per second!

^{* - To do this calculation, I started from the assumption that the same sort is never drawn twice, and therefore, on average, after testing half of the possible sorts, the chance that the algorithm would stumble into the correct sort would be 50%. It turns out that the standard bogosort does not have this restriction, so the average time taken would actually be even worse than this.}

Answer 2

Bogosort, known as stupid Sort, permutation Sort, slowsort, shotgun Sort, Monkey Sort, is used for educational purposes in the disciplines of algorithmic analysis and complexity in order to teach students a paradigm known as "generate and test" that nothing else is: do until you reach the final result. Its complexity is of O(n!)

Basically Bogosort works with the premise: "shuffle the vector (shuffle) again while it is not ordered".

So imagine inefficiency in trying to perform this technique on vectors with many positions? Yes, inefficient because it would do random permutation of elements while not 100% ordered.

An example of implementing Bogosort in C:

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

void embaralhar(int *pV, int n);
bool verificarOrdenacao(int *pV, int n);
void aplicarBogosort(int *pV, int n);

int main(){
    int numeros[] = { 33, 10, 50, -4, 2, 99, -1};
    int i;
    aplicarBogosort(numeros, 7);
    for (i=0; i < 7; i++)
        printf("\n%d ", numeros[i]);

    return EXIT_SUCCESS;
}

bool verificarOrdenacao(int *pV, int n){
    while (--n >= 1) {
        if (pV[n] < pV[n-1])
            return false;
    }
    return true;
}

void embaralhar(int *pV, int n){
    int i, t, r;
    for(i=0; i < n; i++) {
        t = pV[i];
        r = rand() % n;
        pV[i] = pV[r];
        pV[r] = t;
    }
}

void aplicarBogosort(int *pV, int n){
    while (!verificarOrdenacao(pV, n)) embaralhar(pV, n);
}

As a contribution from OS member @Guilherme Lima, follow the video demonstrating how it works in visual terms, to facilitate the abstraction):https://www.youtube.com/watch?v=DaPJkYo2quc