排序网络


最近看《算法导论》时接触到一个比较有趣的概念:排序网络(sorting networks)。什么是排序网络呢?简单来说,排序网络就是通过一系列的比较器(comparators)来调整输入数据的次序,使无序的数据最终变成有序的输出。

一个很自然的问题是,我们已经有了那么多种排序算法,为什么还需要排序网络呢?个人觉得有以下几个原因。

普通的排序算法,不管是简单的冒泡排序、插入排序,还是效率更高的堆排序、归并排序、快速排序等,都是在串行的计算机上实现的。通过信息论或者决策树模型可以证明,基于比较的排序算法在最坏情况下必须要通过 \(\Omega(n \log n)\) 次比较操作才能完成对 n 的数据的排序。因此,具有平均情况时间复杂度 \(\Theta(n \log n)\) 的排序算法已经是最优的了。虽然桶排序、计数排序等可以实现线性时间的排序,但是它们都依赖于输入数据的某些特殊性质,并非通用的排序算法。那么,如何做到比 \(\Theta(n \log n)\) 时间更快的排序呢?既然所需要的比较操作次数无法减少,那么一个可能的方法就是并行化,在同一时间完成多次比较,排序网络就可以做到这一点。

排序网络的另一个优点是适合于硬件实现。观察一下衡量排序网络性能的网络“深度”,会发现它居然和数字电路中的“关键路径”的概念不谋而合。我们知道关键路径决定了数字电路能够工作的速度,而排序网络的深度也决定了它能够以多快的速度完成排序。

我们先来看一个简单的例子:完成对两个输入数据进行排序的网络。

comparator

这个“网络”仅仅由一个比较器组成,如果用数字电路来实现也非常简单,只需要一个比较器和两个多路选择器就能够实现。

有了比较器的基本结构,我们下面就可以构建比较复杂的排序网络了。下面是一个四输入的排序网络结构和排序过程。

SimpleSortingNetworkFullOperation

(图片来自Wikipedia,作者Oskar Sigvardsson

其排序原理如下:前面4个比较器使最大的元素和最小的元素分别移动到最底层和最顶层,最后一个比较器用来调整中间两个元素的次序。

那么如何构建一般的对任意个元素进行排序的网络呢?这可以用递归的方法实现。假设我们已经有一个能完成n个元素的排序的网络,其输出为从小到大排列的n的元素,为了实现能够对n+1个元素进行排序的网络,我们可以把第n+1个元素插入到前面n个有序输出中的正确位置,此时得到的就是n+1个元素的有序排列。这实际上就是插入排序的过程。另一种实现n+1个元素排序的方法是首先找出n+1个元素中最大的元素,将它移动到网络的最底层(通过n个比较器),此时问题的大小就被减小为n,然后用同样的方法递归解决问题。这对应的是冒泡排序的过程。这两种网络的结构如下图所示,我们惊讶地发现,这两种网络的结构居然是一样的!

pyramid sorting network

(图片来自Wikipedia,作者Oskar Sigvardsson

使用上面构造的这种网络来排序n个元素,需要使用n(n-1)/2个比较器,网络的深度(“关键路径”)则是2n-3。那么是否存在效率更高的排序网络呢?答案是肯定的。下面的这种“砖墙”式网络就是对上面网络的一种改进,其正式名称叫做奇偶移项排序网络(Odd-even transposition sorting networks)。它的深度是n。

brick sorting network

更进一步,能否利用排序网络实现比线性更加快速的排序呢?答案同样是肯定的。两种常用的高效排序网络是Batcher奇偶归并排序网络(Batcher odd-even merging network)和双调排序网络(Bitonic sorting network)。它们的比较器数量是 \(\Theta(n \log^2 n)\) ,网络深度是 \(\Theta(\log^2 n)\) 。下面是一个8输入的双调排序网络。这里暂不对其详细介绍,感兴趣的读者可以参考《算法导论》第27章。

Bitonic sorting network

(图片来自 Wikipedia,作者Octotron

说到排序网络,一个不得不提到的原理是0-1原理,它是由大名鼎鼎的Stanford计算机科学教授高德纳(Donald Ervin Knuth)提出的。0-1原理证明了如果一个排序网络能够对任意的0-1序列进行正确的排序,那么它能够对由任意数字组成的序列进行正确的排序。非常有趣吧!这真是让我体会到数学之美的定理。

对于我们学微电子的的学生,排序网络更有特殊的意义。它非常容易通过硬件来实现,具有高度的并行性,因而适合完成在芯片中的排序任务,不管是专用的集成电路芯片还是图形处理单元。《GPU Gems 2》这本书中就讲到了排序网络在nVIDIA GPU中的应用

GPU需要处理大量的数据,而排序是很多数据处理中必要的一步。例如,3D应用程序需要对物体的可见性进行排序,这样才能正确地渲染透明的物体;粒子系统需要按照物体离观察者的远近来进行排序。但是,如果将需要排序的数据从GPU送到CPU进行排序,然后将结果再送回GPU,效率将会很低,无法满足很多实时应用的需求,因此,在GPU中完成排序就成为必需。GPU可以使用大量的运算单元(shader)来进行排序,达到很高的性能。其程序描述需要使用shader language,以后有机会再研究。

其它一些关于排序网络的资料:

Wikipedia上关于排序网络的介绍

Matrix67的写过一篇非常好的介绍排序网络的文章