Bogosort vs bogobogosort [fechado]

Não bogobogosort

A maneira como você implementou seu bogobogosort, na verdade é mais rápido do que o bogosort becau se por alguns motivos:

1. Depois de bogosort k elementos com sucesso, você verifica imediatamente se k+1 são classificados. Isso significa que, se em um embaralhamento anterior, você embaralhou m elementos todos em ordem, depois de classificar os dois primeiros elementos, você alcançará imediatamente m.

   Por exemplo, suponha que você alcance 5 cartas e depois falhe. Você embaralha 5 cartas e começa de novo com 2. Se essas 5 cartas estiverem em ordem, você alcançará imediatamente 6 assim que colocar as 2 primeiras cartas em ordem.

2. Por causa do ponto # 1, seu bogobogosort é na verdade mais rápido do que o bogosort porque ele só precisa classificar n-1 cartões em vez de n . Depois de classificar os cartões n-1, ele verifica a ordem dos cartões n e pode falhar. Mas, ao falhar, ele reorganiza n cartões de modo que cada vez que classifica n-1 cartões, ele tem um 1/n chance de eventualmente ter sucesso. Portanto, o número total de cartas embaralhadas é da ordem de (n-1) * (n-1)! * n, o que simplifica para (n-1) * n!, em comparação com o bogosort que embaralha n * n! cartões.

   Eu acredito que o mesmo princípio se aplica a cada etapa, então o tempo é ainda menor do que (n-1) * n!. Não tenho certeza da matemática exata, mas ao executar seu programa, parece que o bogobogosort é executado aproximadamente ao mesmo tempo que o bogosort com um cartão a menos. Ou seja, Your_bogobogosort (n) = bogosort (n-1).

Um bogobogosort adequado

Reescrevi sua função do bogobogosort para ser assim:

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; } 

A principal diferença aqui é que depois de cada sucesso em que incrementa b, ele reorganiza o baralho para evitar que o ponto nº 1 acima aconteça. Com essa mudança, obtenho uma saída como esta:

% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds. 

Comentários

• De acordo com a descrição na Wikipedia, a primeira parte do bogosort está verificando dados. Se os primeiros N elementos estão em ordem, um bogosort desses N elementos não faz um único embaralhamento. Então, se eu tiver 0 1 2 3 4 6 5 e bogobogosort, vou de bogosort de 2 para 5 elementos sem qualquer embaralhamento, em seguida, embaralhe 6 elementos (e volte para bo gobogosorting 2).
• @pmg Se essa é a definição adequada de bogobogosort, ele é mais rápido do que bogosort (como prova o programa OP ' s) . Eu ' não estou familiarizado com as origens do bogobogosort, mas para que ele " funcione até a morte térmica do universo " como reivindicado, deve ser mais parecido com o que eu escrevi.