Stooge Sortの安定した実装？

Question

これは実際に可能ですか？私はウィキペディアでそれを見つけました。しかし、私はまだプロセスを完全に視覚化できないので、安定させるために何を変えなければならないのか分かりません。

Answer 1

最初に、要素の順序を実際に変更する1つのステップ、Stooge Sortがあることに注意してください：最初のもの。残りのステップはすべて再帰ステップです。いずれかの再帰ステップを変更すると、アルゴリズムの基本的な特性が変更され、このように再帰しないとソートされなくなります（3つの再帰呼び出しは本来 "stoogey"のように見えます）。

最初のステップも非常に単純であり、それを変更することはアルゴリズムの性質も変えるようです。しかし、最初の要素が最後の要素よりも大きい場合は、最初の要素をAと交換します。最後の要素はの前の最後の要素と等しくなります。 1回のパスで見つけることができます。意外にも、内部ループがO（1）の代わりにO（n）であったとしても、Master theoremは、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)); 
       } 
      } 
     } 
    } 
} 

Answer 2

比較ベースのソートアルゴリズムは安定しています。 2つの要素が等しい場合は、元のインデックスを比較するように比較関数を変更するだけです。 stooge sortは比較ベースのソートなので、ここでも同様に適用できます。