bogobogosort가 아님
bogobogosort를 구현 한 방식은 실제로 bogosort becau보다 빠릅니다. 몇 가지 이유가 있습니다.
-
k 요소를 성공적으로보고 정렬 한 후 즉시 k+1 요소가 정렬됩니다. 즉, 이전 셔플에서 m 요소를 모두 순서대로 셔플 한 다음 처음 두 요소를 정렬하면 즉시 m.
예를 들어 카드 5 장에 도달 한 후 실패했다고 가정 해 보겠습니다. 5 장의 카드를 섞은 다음 2부터 다시 시작합니다. 5 장의 카드가 정렬 된 순서로되어 있으면 처음 2 장의 카드를 순서대로 놓는 즉시 6 장에 도달합니다.
-
포인트 # 1 때문에보고보고 소트는 n 대신 n-1 카드를 정렬하기 만하면되기 때문에 실제로보고 소트보다 빠릅니다. . n-1 카드를 정렬 한 후 n 카드의 순서를 확인하고 실패 할 수 있습니다. 하지만 실패하면 n 카드를 다시 섞어서 n-1 카드를 정렬 할 때마다 1/n 결국 성공할 가능성. 따라서 셔플 된 총 카드 수는 (n-1) * (n-1)! * n 순으로 (n-1) * n!로 단순화되며 n * n! 카드.
각 단계마다 동일한 원칙이 적용되므로 시간은 (n-1) * n!보다 훨씬 적습니다. 정확한 계산은 모르겠지만 프로그램을 실행 한 결과 bogobogosort가 카드가 하나 더 적은 bogosort와 거의 같은 시간에 실행되는 것으로 보입니다. 즉, Your_bogobogosort (n) = bogosort (n-1)
적절한 bogobogosort
bogobogosort 함수를 다음과 같이 다시 작성했습니다.
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; }
여기서 중요한 차이점은 b가 증가하는 각 성공 후에는 위의 1 번 지점이 발생하지 않도록 데크를 다시 셔플한다는 것입니다.이 변경으로 다음과 같은 결과를 얻습니다.
% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds.
댓글