模糊排序算法归并稳定性

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 委托给用户。我有运行多次模拟（响应可能意外地是 "wrong" ~1/3 的时间，"wrong" 我的意思是没有通过按错键输入他们的真实偏好）和根据以下标准，排序似乎表现良好：

输出结果足够接近用户偏好（模拟）。
算法及时停止。 10 个项目的列表大约需要 20 个步骤。

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

Answer 1

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

没有。算法总是停止，不管比较如何bad/wrong/unfortunate。

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

这在很大程度上取决于您对 "close enough to the user preference" 的定义。并且可能一个重要的错误是假设用户偏好根本是一种传递关系。

模糊排序算法归并稳定性

Fuzzy sorting algorithm merge stability

javascript

sorting

algorithm

mergesort

stability

上下文

问题