FlagSort - - 분할 및 정복 특정 정렬 알고리즘을 구현 사소한 문제

Question

, 나는 심지어 구글은 알고리즘에 대해 ... 먼저 일부 단어를 도와 싶어하지 않는 문제로 실행 :

사자의 공유는 입력 (배열)을 세 부분으로 분할하는 것입니다. 두 개의 중요한 수 (빨간색과 파란색, 빨간색 < = 파란색을 지정 함)를 선택하면 파티션의 요소는 (1) 둘 다 미만, (2) 중간 및 (3) 두 피봇보다 크다. 이것은 잘 작동하는 부분입니다!

배열을 재귀 적으로 정렬해야합니다. 파티션을 분할하기 전에 임의의 피벗을 사용하여 입력을 분할하므로 def 당 정렬되는 길이 1 또는 2의 입자로 끝납니다. 또는 오히려 아주 쉽게 분류 될 수 있습니다.

이제 문제는입니다. 길이가 3보다 큰 파티션은 하나의 키 값으로 구성됩니다. 피벗을 선택했는지 여부에 관계없이 다시 파티션 된 경우 나중에 모든 요소가 동일한 파티션에 저장되어 결국 스택 오버플로로 실행됩니다. 그 이유는 내가 당신을 도울 수 있다고 생각했기 때문입니다. 나는 이것이 해결책이라고 확신합니다.

필수 Java 코드 조각 : 파티셔닝 - 독일어 디버깅으로 인해 미안하지만 너무 번역하기가 너무 어렵습니다. IntTuple은 두 개의 정수 만 가질 수 있습니다. 너무 어리 석다.

public static IntTuple partition(int[] E, int left, int right, int red, int blue){ 
    if (red > blue) { 
     int v = red; 
     red = blue; 
     blue = v; 
    } 
    System.out.println("Partition Eingabe: " + Arrays.toString(E) + " Links=" + left + " Rechts=" + right + " Rot=" + red + " Blau=" + blue); 
    /* 
    * Es gilt r <= b, also gilt für beliebige x... 
    * ... x < r => x < b 
    * ... x > b => x > r. 
    * 
    * Das Gerüst für diesen Algorithmus wurde kopiert von Folie 7-13 
    */ 
    IntTuple result = new IntTuple (left, right); // rote und blaue Regionen sind leer 
    int u = left; // weiße Region ist leer, die unbekannte == E[left...right] 
    while (u <= result.v2) { 
     System.out.print("E[" + u + "]: "); 
     if (E[u] < red) { 
      System.out.print("rot "); 
      swap(E, result.v1, u); 
      result.v1++; // vergrößere die rote Region 
      u++; // verkleinere die unbekannte Region 
     } else if ((E[u] >= red) && (E[u] <= blue)) { 
      System.out.print("weiß "); 
      u++; // verkleinere die unbekannte Region 
     } else if (E[u] > blue) { 
      System.out.print("blau "); 
      swap(E, result.v2, u); 
      result.v2--; // vergrößere die blaue Region 
     } 
     System.out.print("Partition Schritt: ["); 
     for(int i = left; i < right; i++) 
      System.out.print("" + E[i] + " "); 
     System.out.println("" + E[right] + "]"); 
    } 
    System.out.print("Partition Ausgabe: ["); 
    for(int i = left; i < right; i++) 
     System.out.print("" + E[i] + " "); 
    System.out.println("" + E[right] + "]" + " RotG=" + result.v1 + " BlauG=" + result.v2); 
    return result; 
} 

필수 JavaCode 조각 : 어떤 아이디어에 대해 사전에

private static void flagSort(int[] E, int left, int right){ 
    System.out.println("Sortiere: " + left + " bis " + right); 
    if(left < right - 1) { 
     Random rnd = new Random(); 
     IntTuple v = partition(E, left, right, rnd.nextInt(50), rnd.nextInt(50)); 
     //IntTuple v = partition(E, left, right, E[left], E[left + 1]); 
     flagSort(E, left, v.v1 - 1); 
     flagSort(E, v.v1, v.v2); 
     flagSort(E, v.v2 + 1, right); 
    } else if((left == right - 1) && (E[left] > E[right])) { 
     swap(E, left, right); 
    } 
} 

많은 감사를 정렬!

감사합니다, LDer

더 :

이

private static void flagSort(int[] E, int left, int right, boolean dual){ 
    if(left < right) { // Singleton or empty segments are already sorted! 
     IntTuple v; 
     if(dual) // The last step has produced only a single white partition. 
      // Treat this partition with double pivot 
      v = partition(E, left, right, E[left], E[left]); 
     else // The last step has produced more than one partition, go on normally. 
      v = partition(E, left, right, E[left], E[left + 1]); 
     // Analyze partitions 
     if((left != v.v1) || (right != v.v2)) { 
      // 2 or 3 partitions available. Descend further. 
      flagSort(E, left, v.v1 - 1, false); 
      flagSort(E, v.v1, v.v2, false); 
      flagSort(E, v.v2 + 1, right, false); 
     } else if(!dual) { 
      // Only the white partition is not empty, partition it with double pivot 
      flagSort(E, v.v1, v.v2, true); 
     } // Last case: The only not-empty partition is white after partitioning with double pivot. 
      // Description of the algorithm immediately implies that this consists of only one key value, thus is sorted. 
    } 
} 

는 사람이 더 읽기 버전을 만드는 도울 수 :이 해키 어색 솔루션을 함께했다?

더 :이 하나가 더 나은 방법 같습니다 toto2에

private static void flagSort(int[] E, int left, int right, int offset){ 
    if(left < right) { // Singleton or empty segments are already sorted! 
     IntTuple v = partition(E, left, right, E[left], E[left + offset]); 
     // Analyze partitions 
     if ((left != v.v1) || (right != v.v2)) { 
      // 2 or 3 partitions available. Descend further. 
      flagSort(E, left, v.v1 - 1, 1); 
      flagSort(E, v.v1, v.v2, 1); 
      flagSort(E, v.v2 + 1, right, 1); 
     } else if (offset > 0) 
      // Only the white partition is not empty, partition it with double pivot 
      flagSort2(E, v.v1, v.v2, 0); 
     // Last case: The only not-empty partition is white after partitioning with double pivot. 
     // Description of the algorithm immediately implies that this consists of only one key value, thus is sorted. 
    } 
} 

특별 감사를, 나는 레드/블루 명시 적으로 합격을하지 못하더라도!

더 : 더 임의성, toto2 다시 완전히 지점이 있기 때문에 :

private static void flagSort(int[] E, int left, int right, int offset){ 
    if(left < right) { 
     IntTuple v = partition(E, left, right, E[left + (offset % (right - left))], 
      E[left + ((2 * offset) % (right - left))]); 
     if ((left != v.v1) || (right != v.v2)) { 
      int random = rnd.nextInt(right - left); 
      flagSort(E, left, v.v1 - 1, random); 
      flagSort(E, v.v1, v.v2, random); 
      flagSort(E, v.v2 + 1, right, random); 
     } else if (offset > 0) 
      flagSort(E, v.v1, v.v2, 0); 
    } 
} 

Answer 1

당신이 당신의 파티션 방법을 호출 할 때마다 온, 간단한 일이 발생합니다 파란색과 빨간색 인덱스 항목은 정확히 그들이 속한 곳. 그래서, 당신은 당신의 코드의이 부분을 호출 할 때 :

flagSort(E, left, v.v1 - 1); 
    flagSort(E, v.v1, v.v2); 
    flagSort(E, v.v2 + 1, right); 

이러한 호출이 즉, 파란색과 빨간색 포함 할 수 없습니다 :

flagSort(E, left, v.v1 - 1); 
flagSort(E, v.v1 +1 , v.v2 -1); 
flagSort(E, v.v2 + 1, right); 

Answer 2

IntTuple v = partition(E, left, right, rnd.nextInt(50), rnd.nextInt(50)); 

(50)?현재 파티션의 최소 - 최대 (빨강 - 파랑) 값은 0-49보다 좁습니다. left-right 값뿐만 아니라 red-blue 값을 전달하도록 flagSort를 수정해야합니다.

flagSort가 빨간색 == 파란색으로 호출되면 하위 배열의 값이 동일하고 이미 정렬되어 있으므로 반환 할 수 있습니다.