测试排序函数正确性的最快方法是什么?

compareAndSwap(x[0],x[2]);
compareAndSwap(x[3],x[4]);
compareAndSwap(x[2],x[4]);
compareAndSwap(x[0],x[3]);
compareAndSwap(x[2],x[3]);
compareAndSwap(x[1],x[3]);
compareAndSwap(x[1],x[2]);
compareAndSwap(x[0],x[1]);
compareAndSwap(x[3],x[4]);

pow(2,100) .

x[2]

compareAndSwap(x[0],x[4]);
compareAndSwap(x[1],x[3]);

已尝试为样本数组使用随机数生成器,但不确定其是否可接受:

      std::random_device rd;
      std::mt19937 rng(rd());
      std::uniform_real_distribution<double> dist(0,1);

      for(int k=0;k<500;k++)
      {
        std::vector<double> arraySorted;
        for(int i=0;i<5;i++)
            arraySorted.push_back(dist(rng));

      //sortNetwork(arraySorted.data());

      //if(!std::is_sorted(arraySorted.begin(),arraySorted.end())) 
            throw std::runtime_error("error");
      }

即使这样也会遗漏一些部分。有没有快速的方法来测试排序算法?

如果是1000个元素的数组呢?这些测试是用数学、笔和纸在一些定理和已知算法中进行的,还是用超级计算机进行的?

只是4个元素的一些示例案例:

1 2 3 4   
1 2 4 3   
2 1 3 4    
2 1 4 3   
1 2 0 1                        
1 2 1 0                         
2 1 0 1
2 1 1 0
3 4 2 1                           
3 4 1 2
4 3 2 1
4 3 1 2
1 1 1 1

似乎有超过pow(2,n)的病例。

在生成测试数据时,排序网络是否可以像图形问题一样处理?