No bogobogosort
La forma en que implementó su bogobogosort, en realidad es más rápido que bogosort becau por algunas razones:
-
Después de seleccionar correctamente los elementos k, verifica inmediatamente si k+1 los elementos están ordenados. Esto significa que si en una reproducción aleatoria anterior, mezcló m elementos todos en orden, luego de ordenar los dos primeros elementos llegará inmediatamente a m.
Por ejemplo, suponga que llega a 5 cartas y luego falla. Mezcla 5 cartas y luego comienza de nuevo en 2. Si esas 5 cartas están ordenadas, inmediatamente llegará a 6 tan pronto como ponga las primeras 2 cartas en orden.
-
Debido al punto n. ° 1, su bogobogosort es en realidad más rápido que el bogosort porque solo necesita ordenar n-1 tarjetas en lugar de n . Después de clasificar las tarjetas n-1, verifica el orden de las tarjetas n y puede fallar. Pero si falla, vuelve a barajar n tarjetas para que cada vez que clasifique n-1 tarjetas tenga una 1/n posibilidad de eventualmente tener éxito. Por lo tanto, el número total de cartas barajadas es del orden de (n-1) * (n-1)! * n que se simplifica a (n-1) * n!, en comparación con el bogosort que se baraja n * n! tarjetas.
Creo que se aplica el mismo principio en cada paso, por lo que el tiempo es incluso menor que (n-1) * n!. No estoy seguro de la matemática exacta, pero al ejecutar su programa parece que el bogobogosort se ejecuta aproximadamente al mismo tiempo que el bogosort con una tarjeta menos. Es decir, Your_bogobogosort (n) = bogosort (n-1).
Un bogobogosort adecuado
Reescribí tu función bogobogosort para que sea así:
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; }
La diferencia clave aquí es que después de cada éxito en el que aumenta b, reorganiza el mazo para evitar que suceda el punto # 1 anterior. Con este cambio, obtengo un resultado como este:
% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds.
Comentarios