0001 #include <cstdio>
0002 #include <cstring>
0003 #include <cstdlib>
0004 #include <ctime>
0005 #include "_share/util.h"
0006 #include "UniPrint/print.h"
0007 #include "vector/vector.h"
0008 #include "factorial/fac.h"
0009 
0010 uint64_t passed = 0;
0011 uint64_t done = 0;
0012 uint64_t all = 0;
0013 
0014 int test(Vector<Rank>& A, Rank n) { //排序算法完全测试
0015    if (n < 2) {
0016       print(A); Vector<Rank> X(A); X.sort(); print(X); printf("\n");
0017       for (Rank i = 0; i < X.size(); i++)
0018          if (X[i] != i/2) { print(X); return 1; }
0019       passed++;
0020       if (((passed - done) > 999999) || ((passed - done)*20 > all))
0021          { printf("%.1f%% : %I64d / %I64d\n", 100.*passed/all, passed, all); done = passed; }
0022       return 0;
0023    }
0024    for (Rank i = 0; i < n; i++) {
0025       if (test(A, n-1)) return 1;
0026       swap(A[n % 2 ? 0 : i], A[n-1]);
0027    }
0028    return 0;
0029 }
0030 
0031 int sorterTest(Rank n) {
0032    Vector<Rank> A(n);
0033    for (Rank i = 0; i < n; i++) A.insert(i/2); print(A); printf("\n");
0034    return test(A, n);
0035 }
0036 
0037 int main(int argc, char* argv[]) {
0038    if (2 > argc) { printf("Usage:\n\t%s <sequence length> \a\a\n", argv[0]); return 1; }
0039    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0040    int tests = abs(atoi(argv[1]));
0041    printf("test length = %d\n", tests);
0042    all = facI(tests);
0043    sorterTest(tests); printf("%I64d / %I64d passed\n", passed, all);
0044    return 0;
0045 }