测试排序功能正确性的最快方法是什么？
What is the fastest way of testing correctness of a sorting function?
使用遗传算法，我找到了这个比较列表：
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]);
但我需要测试它是否适用于所有情况。在某些情况下，数组元素的数量（目前为 5 个）也可以增长到 100 个。这意味着要检查的案例数量正在快速增长，超过 pow(2,100).
如果我单独给出一个相反排序的数组作为最坏的情况，那不会检查关于中间元素 x[2] 比较的任何错误。例如，5,4,3,2,1 被一些函数排序为 1,2,3,4,5，通过
compareAndSwap(x[0],x[4]);
compareAndSwap(x[1],x[3]);
单独使用，这肯定不会对许多 5 元素数组的情况进行排序。
尝试了样本数组的随机数生成器，但不确定它是否可以接受：
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) 个案例。
在生成测试数据时，可以将排序网络视为图形问题吗？
虽然您可以检查每个可能列表的每个迭代，但正如您指出的那样，这太慢了。测试不是关于proving the algorithm correct，因为你需要做一个证明。测试是通过测试它可能隐藏的所有地方来减少出现错误的可能性。测试很少尝试涵盖所有可能的 space，而是可能的 类型 错误。
下面是一些练习排序功能的例子。
- 一个空列表
- 单个元素列表
- 全为零的列表
- 有序列表
- 反转列表
- 所有相同元素的列表
- 一个非常大的列表
- 包含奇怪元素的列表（例如，Unicode、负数、重载数字）
然后是错误的输入，应该 return 是错误而不是垃圾。垃圾输入，错误输出。
- 空指针
- 空列表
- 列表太大（如果您的函数有大小限制）
是的，随机化。生成随机有效大小的随机有效列表，然后验证排序结果是否有序。这有助于涵盖您可能错过的任何情况，并避免您可能做出的任何错误假设。这在测试函数 "black box" 时尤为重要，这意味着测试人员不了解其内部结构。每次你 运行 对函数进行更多随机列表时，你就进一步降低了出现错误的可能性。
确保输出使用的随机种子，以便在失败时重复测试。
最后，使用 test coverage 确保您的测试命中代码的所有行和分支。代码可能由 AI 生成，但您仍然可以对其进行覆盖率分析，以确定您的测试差距。 运行 对可能无法阅读的 AI 生成代码进行代码美化将有助于您了解哪些地方需要更多测试。
使用遗传算法，我找到了这个比较列表：
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]);
但我需要测试它是否适用于所有情况。在某些情况下，数组元素的数量（目前为 5 个）也可以增长到 100 个。这意味着要检查的案例数量正在快速增长，超过 pow(2,100).
如果我单独给出一个相反排序的数组作为最坏的情况，那不会检查关于中间元素 x[2] 比较的任何错误。例如，5,4,3,2,1 被一些函数排序为 1,2,3,4,5，通过
compareAndSwap(x[0],x[4]);
compareAndSwap(x[1],x[3]);
单独使用，这肯定不会对许多 5 元素数组的情况进行排序。
尝试了样本数组的随机数生成器，但不确定它是否可以接受：
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) 个案例。
在生成测试数据时，可以将排序网络视为图形问题吗？
虽然您可以检查每个可能列表的每个迭代，但正如您指出的那样，这太慢了。测试不是关于proving the algorithm correct，因为你需要做一个证明。测试是通过测试它可能隐藏的所有地方来减少出现错误的可能性。测试很少尝试涵盖所有可能的 space，而是可能的 类型 错误。
下面是一些练习排序功能的例子。
- 一个空列表
- 单个元素列表
- 全为零的列表
- 有序列表
- 反转列表
- 所有相同元素的列表
- 一个非常大的列表
- 包含奇怪元素的列表（例如，Unicode、负数、重载数字）
然后是错误的输入，应该 return 是错误而不是垃圾。垃圾输入，错误输出。
- 空指针
- 空列表
- 列表太大（如果您的函数有大小限制）
是的，随机化。生成随机有效大小的随机有效列表，然后验证排序结果是否有序。这有助于涵盖您可能错过的任何情况，并避免您可能做出的任何错误假设。这在测试函数 "black box" 时尤为重要，这意味着测试人员不了解其内部结构。每次你 运行 对函数进行更多随机列表时，你就进一步降低了出现错误的可能性。
确保输出使用的随机种子，以便在失败时重复测试。
最后，使用 test coverage 确保您的测试命中代码的所有行和分支。代码可能由 AI 生成，但您仍然可以对其进行覆盖率分析，以确定您的测试差距。 运行 对可能无法阅读的 AI 生成代码进行代码美化将有助于您了解哪些地方需要更多测试。