排序算法,其中成对比较可以返回比-1,0,+ 1更多的信息

Question

大多数排序算法依赖于成对比较,确定A <B,A = B还是A> B.

我正在寻找利用成对比较功能的算法(以及奖励积分,Python中的代码),这种功能可以将更少的东西与更少的东西或更多的东西区分开来.所以也许而不是返回{-1,0,1},比较函数返回{-2,-1,0,1,2}或{-5,-4,-3,-2,-1,0,1 ,2,3,4,5}或甚至是间隔(-1,1)上的实数.

对于某些应用程序(例如接近排序或近似排序),这将使得能够以较少的比较来确定合理的排序.

Answer 1

您可以使用修改后的快速排序.让我解释比较函数返回[-2,-1,0,1,2]时的示例.比如说,你有一个数组A来排序.

创建5个空数组 - Aminus2,Aminus1,A0,Aplus1,Aplus2.

选择A,X中的任意元素.

对于数组的每个元素,将其与X进行比较.

根据结果​​,将元素放在Aminus2,Aminus1,A0,Aplus1,Aplus2阵列中的一个中.

递归地应用于Aminus2,Aminus1,Aplus1,Aplus2(请注意:您不需要对A0进行排序,因为所有元素都等于X).

连接数组以获得最终结果:A = Aminus2 + Aminus1 + A0 + Aplus1 + Aplus2.

Answer 2

确实可以使用额外信息来最小化比较总数.对super_comparison函数的调用可用于进行相当于对常规比较函数的大量调用的推断.例如,a much-less-than b和c little-less-than b暗示a < c < b.

可以将扣除组织成箱或分区,每个箱或分区可以单独分类.实际上,这相当于具有n路分区的QuickSort.这是Python中的一个实现:

from collections import defaultdict
from random import choice

def quicksort(seq, compare):
    'Stable in-place sort using a 3-or-more-way comparison function'
    # Make an n-way partition on a random pivot value
    segments = defaultdict(list)
    pivot = choice(seq)
    for x in seq:
        ranking = 0 if x is pivot else compare(x, pivot)
        segments[ranking].append(x)
    seq.clear()

    # Recursively sort each segment and store it in the sequence
    for ranking, segment in sorted(segments.items()):
        if ranking and len(segment) > 1:
            quicksort(segment, compare)
        seq += segment

if __name__ == '__main__':
    from random import randrange
    from math import log10

    def super_compare(a, b):
        'Compare with extra logarithmic near/far information'
        c = -1 if a < b else 1 if a > b else 0
        return c * (int(log10(max(abs(a - b), 1.0))) + 1)

    n = 10000
    data = [randrange(4*n) for i in range(n)]
    goal = sorted(data)
    quicksort(data, super_compare)
    print(data == goal)

通过使用跟踪模块检测此代码,可以测量性能增益.在上面的代码中,常规三向比较使用133,000个比较,而超级比较功能将调用次数减少到85,000.

该代码还可以轻松地尝试各种比较功能.这将表明天真的n路比较函数对帮助排序几乎没有作用.例如,如果对于大于4的差异,比较函数返回+/- 2,对于差异为4或更小的比率,+/ - 1,则比较次数仅减少5%.根本原因是在开始时使用的课程粒度分区只有少数"近似匹配",其他所有内容都属于"远程匹配".

对超级比较的改进是覆盖对数范围(即如果在十个之内则为+/- 1,如果在一百以内则为+/- 2,如果在一千以内则为+/-).

理想的比较函数是自适应的.对于任何给定的序列大小,比较函数应努力将序列细分为大致相等大小的分区.信息理论告诉我们,这将最大化每次比较的信息位数.

自适应方法也具有良好的直观感.人们首先要分成爱情,比如在做出更多精致的区别之前,比如爱情和爱情.进一步的分区通道应该各自进行更精细和更精细的区分.