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 __int64 passed = 0;
0011 __int64 done = 0;
0012 __int64 all = 0;
0013 
0014 /******************************************************************************************
0015  * 排序算法完全测试
0016  ******************************************************************************************/
0017 int test( Vector<Rank>& A, Rank n ) {
0018    if ( n < 2 ) {
0019       Vector<Rank> X(A); //print(X);
0020       X.sort(); //print(X); printf("\n");
0021       for ( Rank i = 0; i < X.size(); i++ )
0022          if ( X[i] != i/2 ) { print(X); return 1; }
0023       passed++;
0024       if ( ( (passed - done) > 999999 ) || ( (passed - done)*20 > all ) )
0025          { printf( "%.1f%% : %I64d / %I64d\n", 100.*passed/all, passed, all ); done = passed; }
0026       return 0;
0027    }
0028    for ( Rank i = 0; i < n; i++ ) {
0029       if ( test( A, n-1 ) ) return 1;
0030       swap( A[n % 2 ? 0 : i], A[n-1] );
0031    }
0032    return 0;
0033 }
0034 
0035 int sorterTest( Rank n ) {
0036    Vector<Rank> A(n);
0037    for ( Rank i = 0; i < n; i++ ) A.insert( i/2 ); print( A );
0038    return test( A, n );
0039 }
0040 
0041 int main( int argc, char* argv[] ) {
0042    if ( 2 > argc ) { printf( "Usage:\n\t%s <sequence length> \a\a\n", argv[0] ); return 1; }
0043    srand( (unsigned int)time( NULL ) ); //随机种子
0044    //srand( 31415926 ); //固定种子（假种子，调试用）
0045    int tests = abs( atoi( argv[1] ) );
0046    printf( "test length = %d\n", tests );
0047    all = facI( tests );
0048    sorterTest( tests ); printf( "%I64d / %I64d passed\n", passed, all );
0049    return 0;
0050 }