快速排序的杀手级对手 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
RSA加密算法

快速排序的杀手级对手

Hoblovski posted @ 2015年6月22日 03:27 in Discussion with tags 快速排序 论文 对手 在线构造 , 950 阅读

Q  你有经过原作者同意么?

A  没有……这不是翻译。只是将原作者的思想以汉语表现。本文中的思想是原作者的。

Q  原论文是什么?

A  《A Killer Adversary for Quicksort》,可以Google(虽然Google是什么我也不知道

Q  动机?

A  心血来潮。

Q  原文好好的gas solid,你就给改成什么既定未定鬼了?

A  所以不是翻译。窃认为原文的英语和我熟知的英语不同,最开始敝人花了很久脑洞gas solid是什么。请忍耐我的自作主张。

胡诌一句,随机化快排是可以被卡掉的——如果出数据的人是知道你的程序将生成的随机数的未来人的话。

 

 

快速排序的杀手级对手

原著M.D.Mcilroy(Dartmouth College)

Hoblovski

众所周知,快速排序的最坏时间复杂度是O(n²)。人们采用随机化,中位数等方法避免快速排序退化。但Mcllory所写的论文《A Killer Adversary for Quicksort》介绍了一种方法,其使得快速排序的几乎所有实现都退化。本文以整数升序排序为例,对该方法进行简述。

本文并非原论文的纯翻译。想了想,这么小一篇文章没必要用LaTeX玩。

 

一般的快速排序分为三个部分,简单地叙述如下:

一、选择比较基准(下称主元),假设这个过程使用O(1)次比较操作;

二、划分过程:将数组中元素划分为小于、等于、大于基准的三部分;

三、对于小于和大于基准的部分,递归进行上述过程。

显然,如果要让快速排序达到平方级的时间复杂度,必须使得它的划分不平衡。这是该方法的核心思想。该方法观察主元的选择,与此同时对应地安排元素值,使得划分不平衡。其实现是通过一个特殊的比较函数cmp实现的。

注意该方法开始时,元素值是不确定的,排序过程中元素间的大小关系是由cmp函数给出的。算法结束后,元素值才会确定。所以对于每次更新随机种子的随机化快排,该方法无法给出一个hack的数据。然而,若快排选择主元的方法是确定的,譬如未更新随机种子的随机化快排,亦或三者中位数,亦或直接取中间元素,该方法在一次运行后能给出一个hack数据。

 

我们约定下文使用的专有名词:

未定项:至当前阶段,值还未确定的元素。原文称gas item,即“像气体一样漂浮而不定的元素”;

既定项:至当前阶段,值已确定的元素。原文称solid item,即“如固体一样固定的元素”。

 

同时我们规定比较大小的时候:

如果两者都是既定项,直接返回其已确定的值的比较结果;

如果一个是既定项另一个是未定项,则既定项小;

如果两个都是未定项,则比较时,一个会变成既定项,另一个保持未定项。变成既定项的那个元素小于保持未定项的元素。

 

方法如下:

最初所有元素都是未定项。

每次划分过程中,若主元已为既定项,显然不会有新的既定项产生;否则,我们采用如下策略,使得经过最多两次未定项与未定项的比较(下称未-未比较),主元就会变成既定项,从而该次划分中不再有新的既定项产生。第一次未-未比较中,我们随便选择一个未定项变成既定项,另一个变成“主元候补”(pivot candidate)。以后的一次未-未比较,让主元候补变成既定项。

采用该种策略,我们可以保证主元在至多2次未-未比较中就能变成既定项。所以我们可以保证有每次划分都会有n - O(1)个元素大于主元,从而使划分不平衡造成快排退化。

 

为了防止排序算法运行在数据副本上而无法观察到新既定项的产生,我们要排序的不是元素,而是指针(当然,实现中我们用的是下标)。

 

原论文对于快速排序的实现给出了几个如下的限制条件:

一、快速排序是单线程的

二、选择主元使用O(1)次比较,其他所有比较都用于划分

三、划分过程中比较是相邻的(原文contiguous)且总有主元参与的

四、数据操作仅包含比较和复制

五、比较仅涉及输入数据以及其副本

 

最重要的结论:OI中不会出现卡随机化快排的情况(除非出题人SXBK到出一道专卡快排的交互题)

 

C代码由原论文给出,下给出一个Pascal代码(惭愧,吾不怎么会C/C++)。

(********************************
    val:    原数组, 在排序完成后才会构造完成
    ptr:    指向原数组元素下标的指针, 排序的对象
    csol:   既定项(solid item)的个数
    cand:   主元候补的下标. 堆栈中至多有一个qsort过程在使用它, 故其为全局变量
    ccmp:   快速排序中比较次数
    cmp:    比较函数, 返回负数表示val[i] < val[j], 零与正数类似
    aqsort: 快速排序, 同时构造使快排退化的数据
    qsort: 普通的快排, 一种好用且优美的, (Pascal)最主流的实现
********************************)
{$INLINE ON}
program Quicksort_Adversary;

const maxn = 1000017;	

var val,ptr:array[0..maxn] of longint;
    n,csol,cand:longint;
    ccmp:int64;

function cmp(i,j:longint):longint; inline;
begin
    inc(ccmp);
    if (val[i]=n) and (val[j]=n) then
        if i=cand then begin
            inc(csol); val[i]:=csol;
        end else begin
            inc(csol); val[j]:=csol; 
        end;
    if val[i]=n then cand:=i
    else if val[j]=n then cand:=j;
    exit(val[i]-val[j]);
end;

procedure aqsort(l,r:longint);
var i,j,k,o:longint;
begin
    i:=l; j:=r; k:=ptr[l + random(r-l+1)];
    repeat
        while cmp(ptr[i],k) < 0 do inc(i);
        while cmp(ptr[j],k) > 0 do dec(j);
        if i <= j then begin
            o:=ptr[i]; ptr[i]:=ptr[j]; ptr[j]:=o;
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then aqsort(i,r);
    if j > l then aqsort(l,j);
end;

procedure qsort(l,r:longint);
var i,j,k,o:longint;
begin
    i:=l; j:=r; k:=ptr[l + random(r-l+1)];
    repeat
        while val[ptr[i]] < val[k] do inc(i);
        while val[ptr[j]] > val[k] do dec(j);
        if i <= j then begin
            o:=ptr[i]; ptr[i]:=ptr[j]; ptr[j]:=o;
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then qsort(i,r);
    if j > l then qsort(l,j);
end;

procedure ainit;
var i:longint;
begin
    readln(n);
    for i:=1 to n do begin
        val[i]:=n; ptr[i]:=i;
    end; readln;
    ccmp:=0; csol:=0; cand:=0;
end;

procedure init;
var i:longint;
begin
    readln(n);
    for i:=1 to n do begin
        read(val[i]); ptr[i]:=i;
    end; readln;
end;

procedure answer;
var i:longint;
begin
    for i:=1 to n-1 do write(val[i],' '); writeln(val[n]);
    for i:=1 to n-1 do write(val[ptr[i]],' '); writeln(val[ptr[n]]);
    writeln(ccmp);
end;

begin
    assign(input,'sort.in'); reset(input);
    ainit;
    close(input);
    aqsort(1,n);
    assign(output,'sort.out'); rewrite(output);
    answer;
    close(output);
end.

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter