Bogosort - what is this?

Bogosort is an algorithm that consists 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 necessary until by pure luck and chance , random ordering of elements turns out to be correct. Even partially ordered or almost ordered ordinances are completely and blindly discarded in their entirety and do not end up helping.

The result is that the larger the array, the greater the amount of luck you have to have for correct ordering to appear at random whim . Strictly, 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 somehow flawed). Considering that there are no statistical errors in the random order generator, the probability that any given randomly generated order will be (which gives a time complexity of the average case of , where is the number of array elements.

How much is ,theprobabilityofsuccess?Well,lookatthefollowingtable:

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

How long would this take? Well let's assume your machine is super fast and is able to shuffle and test if 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 the smaller ones, but to maintain a bit of optimism, let's assume that large arrays take the same time to be shuffled and tested than the smaller ones). So how long would it take 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 doing 1 billion tests per second!? I think it's clear why bogosort is an inefficient algorithm!

And to see the scale of inefficiency, just see that to order 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 time skips for four and a half years. This is because the time growth is worse than exponential in the size of the input. And look, we're using a super-machine that manages to shuffle the array and see if it's sorted a billion times a second!

* - In order to do this calculation, I assumed that the same ordering is never randomized twice, and therefore, on average, after testing half the possible orderings, the chance of the algorithm failing the correct ordering would be 50%. It happens that the standard bogosort does not have this restriction, so the average time it takes is actually even worse than that.

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

So, imagine the inefficiency when trying to perform this technique on vectors with many positions? Yes, inefficient because it would make random permutation of elements as long as it was not 100% ordered.

An example implementation of 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 of the PT member PT @Guilherme Lima, follow the video   demonstrating how it works in visual terms, to facilitate the   abstraction): link