javascript - 模糊排序算法归并稳定性

Question

上下文

我正在实现一项心理测试，向用户展示成对的图像，用户必须指出他们喜欢哪一个。他们用 A 或 L 键响应他们的偏好。如果图像的数量非常大，那么比较所有可能的对对个人来说是相当苛刻的 (O(n^2))。

问题

我破解了合并排序算法 here以大大减少比较次数。结果如下:

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}


function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (getUserPreference(left[0],right[0])) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

其中函数 getUserPreference 委托(delegate)给用户。我已经运行了多个模拟(其中响应可能意外地“错误”~1/3 的时间，并且“错误”我的意思是没有通过按错键输入他们的真实偏好)并且排序似乎表现良好根据以下标准:

• 输出结果足够接近用户偏好(模拟)。
• 算法及时停止。约 20 个步骤即可列出 10 个项目。

我想知道的是，算法高手能否告诉我该算法是否有可能完全无法停止或逼近输入解。

Answer 1

Is there any chance that this algorithm will completely fail to stop?

没有。算法总是会停止，无论比较有多糟糕/错误/不幸。

The algorithm stops in good time. ~20 steps for a list of 10 items.

对于 10 个项目，最好的情况是 15 次比较，最坏的情况是 25 次比较。一般来说，merge sort平均需要 O(n log n) 个步骤。

Is there any chance that this algorithm will completely fail to approximate the input solutions

这在很大程度上取决于您对“足够接近用户偏好”的定义。一个重要的错误可能是假设用户偏好是一种传递关系。