algorithm - Lomuto 的分区，稳定与否？

Question

我试着在网上和我的算法书中搜索QSort Partition的Lomuto's specific solution是否stable or not(我知道Hoare的版本不稳定)但我没有找到准确的答案。
所以我试着做同样的例子，它看起来很稳定。但我没有证明。你可以帮帮我吗？如果不稳定，能不能给我找个输入的例子？

Answer 1

我将把“使用 Lomuto 分区的快速排序”解释为引用来自 here (slides 21–22) 的算法。 .

此算法在数组 [a, b, c] 上不稳定，其中 c <a = b。

---

我通过在 Python 中实现快速排序算法找到了这个反例，因此(就像 Python 的内置排序一样)它采用 key 函数。通过提供适当的键函数，我可以让排序认为某些元素是相同的，但我仍然可以区分它们。然后这只是尝试大量排列和发现不稳定性的问题。下面的代码当然没有穷尽所有可能的测试(人们可能想尝试两个以上相同的元素，或多组相同的元素)，但在这种情况下已经足够好了。

def lomuto(A, key=lambda x:x):
    def partition(A, p, r):
        i = p - 1
        pivot = A[r]
        for j in range(p, r):
            if key(A[j]) <= key(pivot):
                i += 1
                A[i], A[j] = A[j], A[i]
        A[i+1], A[r] = A[r], A[i+1]
        return i + 1

    def quicksort(A, p, r):
        if p < r:
            q = partition(A, p, r)
            quicksort(A, p, q-1)
            quicksort(A, q+1, r)

    quicksort(A, 0, len(A) - 1)

def test_stability(f, n):
    """Try to discover if the sorting function f is stable on n inputs;
printing the first counterexample found, if any."""
    import itertools
    for i in range(n - 1):
        def order(P): return P.index((i, 0)) < P.index((i, 1))
        array = [(j, 0) for j in range(n - 1)] + [(i, 1)]
        for P in map(list, itertools.permutations(array)):
            Q = P[:] # take a copy
            f(Q, key=lambda x: x[0])
            if order(P) != order(Q):
                print(P, '->', Q)
                return

>>> test_stability(lomuto, 3)
[(1, 0), (1, 1), (0, 0)] -> [(0, 0), (1, 1), (1, 0)]