排序网络

排序网络 Sorting Network - matrix67

1、比较器与排序网络

一般的排序算法都是给定了数据再排序,排序效率很大程度上取决于数据的好坏。我们今天所介绍的是一个完全不同的排序方法,它可以在“暗箱”里对数据进行排序(即你不必知道实际数据是什么),换句话说这种排序方法不依赖于数据(Data-Independent),所有比较操作都与数据无关。你甚至可以立即忘掉前面的比较结果,因为对于所有可能的数据这类排序算法都能得到正确答案并且排序步骤完全相同。本文结束后再回过头来看这段话你将有更深的认识。

我们设置一个暗箱,暗箱左边有n个输入口,暗箱右边有n个输出口。我们需要设计一个暗箱使得,任意n个数从左边输进去,右边出来的都是有序的。图1显示了有4个输入的暗箱。


暗箱里唯一允许的元件叫做“比较器”(Comparator),每个比较器连接两个元素,当上面那个比下面那个大时它将交换两个元素的位置。也就是说,每经过一个比较器后,它的两端中较小的一个总是从上面出来,较大的总是到了下面。

图2显示了一种包含4个比较器的暗箱系统。当输入数据 3,1,4,2 通过这个系统时,输出为1,3,2,4,如图3所示。这种暗箱结构叫做比较网络(Comparator Network)。如果对于任意一个输入数据,比较网络的输出都是有序的,那么这个比较网络就叫做排序网络(Sorting Network)。显然,我们例子中的比较网络不是一个排序网络,因为它不能通过 3,1,4,2 的检验。

冒泡排序是一个彻头彻尾的排序网络模型。它的比较就是无条件的,不管数据怎样冒泡排序都是不断比较相邻元素并把较小的放到前面。如图4。我们通常不认为插入排序是排序网络,因为插入排序的比较次数取决于数据的有序程度。

传统的计算机一次只能处理一个比较。排序网络真正的研究价值在于,假如有机器可以同时处理多个比较器,排序的速度将大幅度提高。我们把比较器的位置稍微移动一下,把那些互不冲突(处理的元素不同)的比较器压缩到一层(Stage)(图5),这样整个排序过程压缩为了 2n-3 层,图4为 n(n-1)/2 层。

我们自然又想,排序网络需要的层数能否少于 2n-3。我们想到,图5的左下角和右下角似乎有些空,我们期望能在这些位置加一些比较从而减少层数。图6给出了一个只有 n 层的排序网络,这叫做奇偶移项排序(Odd-even Transposition Sort)。我们下文将证明它确实是一个排序网络。(图6的排序安排类似三阶矩阵求行列式的一种方法 Sarrus 规则

2、0-1原理

给出一个比较网络,怎样判断它是不是一个排序网络?

传统的做法是枚举所有 n 的排列来验证,一共要考虑 n! 种情况。

下面我们介绍排序网络理论里最重要的结论:0-1原理( 0-1 Principle)。使用这个原理来验证排序网络只需要考虑 2^n 种情况。(言外之意:2^n < n!

0-1原理告诉我们,如果所有的01序列能够通过比较网络排出顺序,那么这足以说明该网络为排序网络。证明过程很简单。为了证明这个结论,我们证明它的逆否命题(逆否命题与原命题同真假,离散数学用在这😂):如果一个比较网络不是排序网络,那么至少存在一个01序列不能被排序。我们给出一种算法,这个算法可以把任何一个不能被排序的输入数据转化为一个不能被排序的01序列。

在最初的例子(图3)中,输入数据 3,1,4,2 的输出为 1,3,2,4,没有成功地排出顺序,从而判断出该网络不是排序网络。这说明,输出结果中存在逆序对(左边某个数大于右边的某个数)。我们从输出结果中找出一个逆序对来。例子中,(3,2) 就是我们要找的逆序对。现在,我们把输入中所有小于数字3(左边那个数)的数都变成0,把所有大于等于3的数都变成1(根据逆序对设置阈值)。这样,3,1,4,2 就变成了 1,0,1,0。显然,把得到的这个01序列输入进去,原来曾经发生过交换的地方现在仍然会交换,原来不曾交换的地方现在也同样不会发生交换(当两个0或两个1进行比较时,我们既可以认为它们不交换,也可以看成它们要互相交换,反正都一样)。最后,该01序列输出的结果中,本来3的位置现在还是1,原来2的位置现在仍然是0,逆序对仍然存在。因此,只要一个比较网络不是排序网络,那么总可以找到一个01序列不能被排序。等价地,如果所有的01序列都能被排序了(没有逆序对),这个比较网络也就是排序网络了。

3、证明奇偶移项排序的正确性

我们用 0-1原理 来证明奇偶移项排序的正确性。

我们对 n 进行数学归纳证明。

  • n=2 时(一个“工”字)显然是排序网络。
  • 图7中是n=8的情况。我们假设对于所有n<=7,奇偶移项排序网络都是正确的。我们同时假定所有输入数字非0即1,下面我们说明n=8时所有的01序列都能被正确排序。

假设最后一个数是1(图7),那么这个1将始终排在最后不参与任何交换操作,对前面7个数没有任何影响。除去无用的灰色部分,剩下的就是n=7这一规模较小的子排序网络,由归纳假设则n=8也是排序网络;

假设最后一个数是0(图8),那么在每一次比较中这个0都会被提到前面去(前面说过,两个0之间交不交换是一回事)。蓝色的箭头表示每个数跑到了什么位置。你会发现除最后一个数以外前7个数之间的比较器又构成了n=7的情况。

综上,奇偶移项排序是排序网络。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,293评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,604评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,958评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,729评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,719评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,630评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,000评论 3 397
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,665评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,909评论 1 299
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,646评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,726评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,400评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,986评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,959评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,996评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,481评论 2 342

推荐阅读更多精彩内容