如何测试仅用5次比较的四数排序系统？求最小测试输入序列

问题背景 #

我有一个通过5次比较实现四数排序的系统，采用一系列MinMax比较器模块（每个模块接收两个数字，输出最小值和最大值）。系统流程如下：

• 初始并行使用两个MinMax比较器，分别比较a与b、c与d；
• 将前一步输出的最小值和最大值输入另外两个MinMax比较器，确定全局最小值和最大值；
• 最后用一个MinMax比较器比较次小值和次大值。

需要设计最小输入序列，验证系统所有组件（MinMax比较器及连接）的完整性，确保无故障。

最小测试输入序列 #

最小输入序列为：[1,2,3,4] 和 [4,3,2,1]，仅这两组输入即可完成全组件验证。

验证逻辑说明 #

覆盖所有MinMax比较器的功能 #

系统共有5个MinMax比较器，每个都需要验证“左小右大”和“左大右小”两种工作状态，才能确认功能正常：

1. 输入[1,2,3,4]的验证场景
   • 第一步：比较器1处理1和2（左小右大），比较器2处理3和4（左小右大）；
   • 第二步：比较器3接收前两个最小值1和3（左小右大），比较器4接收前两个最大值2和4（左小右大）；
   • 第三步：比较器5接收中间值2和3（左小右大）。
     这组输入覆盖了所有比较器的正向比较逻辑。
2. 输入[4,3,2,1]的验证场景
   • 第一步：比较器1处理4和3（左大右小），比较器2处理2和1（左大右小）；
   • 第二步：比较器3接收前两个最小值3和1（左大右小），比较器4接收前两个最大值4和2（左大右小）；
   • 第三步：比较器5接收中间值3和2（左大右小）。
     这组输入覆盖了所有比较器的反向比较逻辑。

验证连接的正确性 #

两组输入的正确输出均为[1,2,3,4]，如果任何环节的连接出现错误（比如某一步输入接反），最终排序结果会异常。例如若第二步比较器3的输入接成了最大值和最小值，第一组输入的输出就会出错。

为何是最小序列？ #

单个输入只能覆盖比较器的一种工作状态，无法验证其反向比较的有效性（比如某个比较器只能处理左小右大的情况，反向输入时失效）。两组输入刚好覆盖所有比较器的核心工作场景，无冗余，是能完成全验证的最小规模。

内容的提问来源于stack exchange，提问作者MaROM