무작위 파티션을 사용하는 QSort

Question

다음 "qsort"구현은 "Foundations of Algorithms"라는 책의 내용이므로 올바른 것으로 판단됩니다. 아래 자바 구현입니다. 작동하지 않습니다. 문제는 파티션을 임의로 선택하면 생성 된 파티션이 올바르지 않다는 것입니다. 나는 누군가가 내가 뭘 잘못 말해 줄 수 바라고 :

밥

import java.util.*; 
public class qsort { 
    public static void main(String []args) 
    { 
     int []a1 = { 1, 2, 3, -4, -5, 6, 7 }; 
     sort(0, a1.length-1, a1); 
     printarray (a1); 

    } 
static void sort(int low, int high, int []a) 
{ 
    if (low < high) { 
     int p = part(low, high, a); 
     System.out.println(" p = " + p); 
     printarray(a, low, p); 
     System.out.println(); 
     sort(low, p-1, a); 
     printarray(a, p, high); 
     System.out.println(); 
     sort(p+1, high, a); 
    } 
} 
static int part(int low, int high, int [] S) { 
     int i; 
     int j; 
     int randspot; 
     int pivotitem; 
     int pivotpoint; 
     Random random = new Random(456); 
     randspot = random.nextInt(high-low +1)+low; 
     pivotitem = S[randspot]; 
     j = low; 
     for (i = low + 1; i <= high; i++) 
      if (S[i] < pivotitem){ 
       j++; 
       int temp = S[j]; 
       S[j] = S[i]; //exchanges S[i] and S[j] 
       S[i] = temp; 
      } 
     pivotpoint = j; 
     int temp = S[low]; 
     S[low] = S[pivotpoint]; 
     S[pivotpoint] = temp; 
     return pivotpoint; 
    } 

static void printarray (int [] Test){ 
    for (int i = 0; i<Test.length; i++){ 
     if (i !=0 && i%10==0) 
      System.out.println(); 
     System.out.print(Test[i]+ "\t"); 

    } 
} 
static void printarray (int [] Test, int low, int high){ 
    for (int i = low; i<high; i++) 
     System.out.print(Test[i]+ "\t"); 
    } 
} 

Answer 1

당신은 첫째로 낮은 인덱스 요소와 피벗 요소를 교체 할 필요가 다음 다른 작업을한다. 다음 코드 블록에서 추가 한 코드를 확인하십시오.

static int part(int low, int high, int [] S) { 
    int i; 
    int j; 
    int randspot; 
    int pivotitem; 
    int pivotpoint; 
    Random random = new Random(456); 
    randspot = random.nextInt(high-low +1)+low; 
    System.out.println(" p = " + randspot); 
    System.out.println(" value = " + S[randspot]); 
    pivotitem = S[randspot]; 
    //---------------Start code block 
    int temp1 = S[randspot]; 
    S[randspot] = S[low]; 
    S[low] = temp1; 
    //---------------End code block 
    j = low; 
    for (i = low + 1; i <= high; i++) 
     if (S[i] < pivotitem){ 
      j++; 
      int temp = S[j]; 
      S[j] = S[i]; //exchanges S[i] and S[j] 
      S[i] = temp; 
     } 
    pivotpoint = j; 
    int temp = S[low]; 
    S[low] = S[pivotpoint]; 
    S[pivotpoint] = temp; 
    return pivotpoint; 
}