这个 "attack"是否真的会导致快速排序降级为二次运行时间，即使项目已被随机打乱？

Question

A Killer Adversary for Quicksort声称有一种方法可以将任何快速排序实现减少到二次时间。我想这意味着它总是会生成一个列表，该列表总是需要 O(n^2) 才能运行。这是在说些什么，因为即使 Quicksort 的最坏情况为 O(n^2)，它通常运行 O(nlogn)。作者声称，即使在调用快速排序之前对数组进行随机打乱，这仍然有效。这怎么可能？我不懂 C，但这是程序的先决条件和代码

The quicksort will be vulnerable provided only that it satisfies some mild assumptions that are met by every implementation I have seen: 1. The implementation is single-threaded. 2. Pivot-choosing takes O (1) comparisons; all other comparisons are for partitioning. 3. The comparisons of the partitioning phase are contiguous and involve the pivot value. 4. The only data operations performed are comparison and copying. 5. Comparisons involve only input data values or copies thereof.

#include <stdlib.h>

int *val; /* item values */
int ncmp; /* number of comparisons */
int nsolid; /* number of solid items */
int candidate; /* pivot candidate */
int gas; /* gas value */

#define freeze(x) val[x] = nsolid++

int cmp(const void *px, const void *py) /* per C standard */
{
    const int x = *(const int*)px;
    const int y = *(const int*)py;
    ncmp++;
    if(val[x]==gas && val[y]==gas)
    {
        if(x == candidate)
            freeze(x);
        else
            freeze(y);
    }
    if(val[x] == gas)
        candidate = x;
    else if(val[y] == gas)
        candidate = y;
    return val[x] - val[y]; /* only the sign matters */
}

int antiqsort(int n, int *a)
{
    int i;
    int *ptr = malloc(n*sizeof(*ptr));
    val = a;
    gas = n - 1;
    nsolid = ncmp = candidate = 0;
    for(i=0; i<n; i++) {
        ptr[i] = i;
        val[i] = gas;
    }
    qsort(ptr, n, sizeof(*ptr), cmp);
    free(ptr);
    return ncmp;
}

一般方法对满足某些非常温和和现实假设的任何快速排序的实现都有效——甚至是随机化的。

他所说的随机化是指随机枢轴选择还是随机化输入结构？

Answer 1

本文使用的模型假设攻击者不仅可以控制数据，还可以控制比较功能。本质上，比较函数依赖于数据，假装快速排序总是碰巧选择一个非常糟糕的主元。对于对手来说，这是一种非常强大的能力。