Lomuto的分区算法是稳定的吗？

Question

我曾经在网上和算法书中搜索过，想知道 Lomuto's 特定解决方案的 QSort Partition 是否是 稳定的（我知道 Hoare's 版本是不稳定的），但我没有找到确切的答案。
所以我尝试做了一些例子，看起来是稳定的。但我没有证明它。 你能帮我吗？ 如果它不稳定，你能找到一个输入示例吗？

- Gengiolo

Answer 1

我将解释“Lomuto分区的快速排序”是指来自这里（幻灯片21-22页）的算法。

当数组[a, b, c]满足c < a = b时，此算法在排序时不稳定。

---

我通过使用Python实现了Quicksort算法，并添加了一个类似于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)]

- Gareth Rees

---

不用客气。你可能想好好思考一下我是如何发现这个例子的... - Gareth Rees

上面的代码中，lomuto到底是什么？（我没有看到它被定义）。它似乎是执行分区的函数，但它需要接受key吗？ - Josh

@Josh：这是使用Lomuto的分区方法实现的快速排序，基于我提供链接的幻灯片。很容易自己编写！ - Gareth Rees

另外，在示例 [a,b,c] 中，如果 c < a = b，那么这只是简单地将跟踪较大元素集结束的索引向前推进（然后将枢轴移动到开头），而不会改变 a 和 b 的顺序吗？ - Josh

谢谢@GarethRees，我同意并感谢您的快速回答。我现在正在自己做这件事。 - Josh

留下一个备忘录以供将来参考：这个答案用一个例子说明了Lomuto分区算法在处理相同元素时会使输出顺序不正确的精确时刻。 - Josh

Answer 2

这取决于效率。

以下是来自维基百科的伪代码。

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

这里是Java的实现。

    public static <E> void lomuto(final List<E> list, final Comparator<? super E> comparator) {
        LOMUTO_SWAP_COUNTER.remove();
        LOMUTO_SWAP_COUNTER.set(new LongAdder());
        sort(list,
             comparator,
             (l, c) -> {
                 assert !l.isEmpty();
                 final int p = l.size() - 1;
                 int i = 0;
                 for (int j = 0; j < l.size() - 1; j++) {
                     if (c.compare(l.get(j), l.get(p)) < 0) { // < vs <=
                         swap(l, j, i++);
                         LOMUTO_SWAP_COUNTER.get().increment();
                     }
                 }
                 swap(l, p, i);
                 return i;
             });
    }

使用以下数据，

[Three(3), John(2), Jane(2), One(1)] // original unsorted

上述实现不稳定，会交换2次。

[One(1), Jane(2), John(2), Three(3)] // unstable, with 2 swaps

当您将 c.compare(l.get(j), l.get(p)) < 0 替换为 c.compare(l.get(j), l.get(p)) <= 0 时，

此实现稳定输出交换 3 次。

[One(1), John(2), Jane(2), Three(3)] // stable, with 3 swaps

- Jin Kwon