ランダムなパーティションを持つQSort

Question

以下のqsortの実装は、 "Foundations of Algorithms"の本ですので、正しいと思われます。以下は私のJavaでの実装です。それは動作しません。問題は、パーティションをランダムに選択すると、生成されたパーティションが正しくないことです。私は、誰かが私が間違っているのものを私に伝えることができることを期待しています：

ボブ

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; 
}