Stooge Sort의 안정적인 구현은 무엇입니까?

Question

실제로 가능합니까? 나는 위키피디아에서 불충분 한 종류의 것을 발견했지만, 아직 프로세스를 완벽하게 시각화 할 수 없으므로 안정화시키기 위해 무엇을 바꾸어야하는지 알지 못합니다.

Answer 1

먼저 요소의 순서를 변경하는 단 하나의 단계, 즉 Stooge Sort이 있다는 점에 유의하십시오. 나머지 단계는 모두 재귀 단계입니다. 재귀 단계를 변경하면 알고리즘의 근본적인 특성이 바뀌므로 이러한 방식으로 재귀 적으로 재귀 적으로 반복하지 않으면 더 이상 통계적으로 정렬되지 않습니다 (3 개의 재귀 호출은 전형적인 "stoogey"처럼 보입니다).

첫 번째 단계는 또한 매우 간단하고 알고리즘의 특성을 변경하는 것처럼 보일 것입니다. 그러나 초기 요소가 최종 요소보다 큰 경우 첫 번째 요소를 A과 바꿔서 앞에있는 마지막 요소와 같습니다.이 요소는 초기 요소와 같습니다. 단일 패스를 통해 찾을 수 있습니다. 놀랍게도 내부 루프가 O (1) 대신 O (n)인데도 Master theorem은 O (n^2.71)에서 복잡성이 동일하다는 것을 보여줍니다. 또한 모든 요소가 고유하다면 원래 Stooge 정렬에서와 같은 순서로 스왑이 발생하므로이 버전을 가까운 사촌으로 만들 수 있습니다.

왜이 버전이 안정적인 지 신속하게 파악하려면 두 개의 동일한 요소를 재정렬하여 "잘못된 스왑"으로 간주하십시오. 우리는 위의 방법을 사용하여 불량 스왑이 없음을 주장합니다. 그 이유는 스왑의 경우 두 요소 사이에 요소가 하나도 없다는 것을 알기 때문입니다. 같은 원소가 같은 순서로 남아 있기 때문에 알고리즘은 안정적이다.

알고리즘이 정확하다는 증거는 원래 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

비교 기반 정렬 알고리즘은 안정적으로 만들 수 있습니다. 두 요소가 같으면 비교 함수를 변경하기 만하면 원래 색인을 대신 비교합니다. 병사 정렬은 비교 기반 정렬이기 때문에 여기에 적용 할 수 있습니다.