一种比较器排序网络正确性验证方法

摘要

比较器排序网络[1](CSN)是一种执行并行排序的专用并行结构,验证一个CSN的正确性非常必要,本文基于[0,1]原理,给出一个验证排序网络的方法并用Java语言进行了实现。第1节介绍CSN及[0,1]原理,第2节介绍验证给定排序网络正确性的算法及实现,第3节总结全文。1比较器网络和[0,1]原理[1]定义1。给定n个数的序列a1,a2,..an,找出一种置换,能将该序列映射到一个非降的序列,此过程称为排序(Sorting)。