6

Lomuto のQSort パーティションの特定のソリューションが安定しているかどうか(Hoare のバージョンが不安定であることはわかっています) を Web とアルゴリズムの本で検索しようとしましたが、正確な答えが見つかりませんでした。
だから私は同じ例を作ろうとしましたが、安定しているようです。しかし、私はそれを示しませんでした。私たちを手伝ってくれますか？安定していない場合は、入力の例を見つけてもらえますか?

4

2 に答える 2

8

「ロムートのパーティションを使ったクイックソート」は、ここからのアルゴリズムを指していると解釈します (スライド 21 ～ 22)。

このアルゴリズムは、 c < a = bである配列 [ a , b , c ]では不安定です。

この反例は、(Python の組み込みソートのように) 関数を取るように Python でクイックソート アルゴリズムを実装することで見つかりましたkey。適切なキー関数を提供することで、特定の要素が同一であるとソートに認識させることができますが、それらを区別することはできます。次に、多くの順列を試して不安定性を見つけるだけです。以下のコードは確かに可能なテストを使い果たすわけではありません (2 つ以上の同一の要素、または同一の要素の複数のセットを試したい場合があります) が、この場合は十分でした。

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)]
于 2011-07-10T13:37:09.240 に答える