1

それは実際に可能ですか？ウィキペディアで非効率な並べ替えで見つけましたが、プロセスを完全に視覚化することはまだできないため、安定させるために何を変更する必要があるかわかりません。

4

2 に答える 2

3

比較ベースの並べ替えアルゴリズムは、安定させることができます。単純に比較関数を変更して、2 つの要素が等しい場合に元のインデックスを比較するようにします。手先並べ替えは比較ベースの並べ替えであるため、ここでも適用できます。

于 2012-05-13T20:41:32.333 に答える
0

まず、要素の順序を実際に変更するStooge Sortのステップは 1 つだけであることに注意してください。最初のステップです。残りのステップはすべて再帰ステップです。再帰ステップのいずれかを変更すると、アルゴリズムの基本的な特性が変更され、この方法で再帰しなければ手先並べ替えではなくなります (3 つの再帰呼び出しは、典型的には「手先が器用」に見えます)。

最初のステップも非常にシンプルで、これを変更するとアルゴリズムの性質も変わるようです。しかし、それを微調整することができます: 最初の要素が最終要素より大きい場合、最終要素に等しい最初の要素Aを、最初の要素に等しいA の前の最後の要素と交換します。シングルパス。驚くべきことに、内側のループがO(1) ではなくO( n ) になったとしても、マスター定理は複雑さが O( n ^2.71) で同じままであることを示しています。また、すべての要素が一意である場合、元の Stooge Sort と同じシーケンスのスワップが発生することも事実であり、このバージョンは近い従兄弟になります。

このバージョンが安定している理由を簡単に説明するには、2 つの等しい要素の並べ替えが「悪いスワップ」であると考えてください。上記のアプローチを使用すると、悪いスワップはないと主張します。その理由は、どのスワップでも、2 つの要素の間にいずれかの要素に等しい要素がないことがわかっているからです。等しい要素は同じ順序のままであるため、アルゴリズムは安定しています。

アルゴリズムが正しいという証明は、元の Stooge Sort の正しい証明に似ています。これはよくある宿題の質問なので、公開したくありませんが、帰納仮説から導かれます。

微調整の説明が少し簡潔だった場合、Java 実装が続きます。

import java.util.Arrays;
import java.util.Random;

public class StableStooge {
    public static class FooBar implements Comparable<FooBar> {
        public final int foo;
        public final int bar;

        public FooBar(int foo, int bar) {
            this.foo = foo;
            this.bar = bar;
        }

        @Override
        public int compareTo(FooBar arg0) {
            return foo - arg0.foo;
        }

        public String toString() {
            return foo +":"+bar;
        }
    }

    private static void sort(Comparable[] c, int start, int end) {
        if (start >= end) return;
        if (c[start].compareTo(c[end]) > 0) {
            // Find the first thing X equal to end and the last thing Y which is before X and equal to start
            int lastindex = end;
            int firstindex = start;
            for (int i = start + 1; i < end; i++) {
                if (c[end].compareTo(c[i]) == 0) {
                    lastindex = i;
                    break;
                } else if (c[start].compareTo(c[i]) == 0) {
                    firstindex = i;
                }
            }
            Comparable tmp = c[firstindex];
            c[firstindex] = c[lastindex];
            c[lastindex] = tmp;
        }
        // Recurse
        if (end - start + 1 >= 3) { 
            int third = (end - start + 1) / 3;
            sort(c, start, end-third);
            sort(c, start+third, end);
            sort(c, start, end-third);
        }
    }

    public static void sort(Comparable[] c) {
        sort(c, 0, c.length-1);
    }

    public static void main(String[] args) {
        FooBar[] test = new FooBar[100];
        FooBar[] testsav = new FooBar[100];
        Random r = new Random();
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < test.length; j++) {
                test[j] = new FooBar(r.nextInt(10), j);
                testsav[j] = test[j];
            }
            sort(test);
            // verify
            for (int j = 1; j < test.length; j++) {
                if (test[j].foo < test[j-1].foo) {
                    throw new RuntimeException("Bad sort");
                }
                if (test[j].foo == test[j-1].foo && test[j].bar <= test[j-1].bar) {
                    throw new RuntimeException("Unstable sort: "+Arrays.toString(testsav)+" sorted improperly to "+Arrays.toString(test));
                }
            }
        }
    }
}
于 2012-05-14T07:29:56.153 に答える