データ構造とアルゴリズムの本からクイックソートに取り組んでいます。この本では、クイックソート方法と、クイックソートで使用するホアパーティションがリストされています。hoare パーティションが配列で範囲外の数値を使用しているという問題があるようです。8 を使用するか、修正しようとすると -1 になります。書籍の擬似をJavaに正しく変換していますか?
クイックソートの疑似コード
QuickSort(A, p, r)
if p<r
q = partition(A, p, r);
QuickSort(A, p, q - 1);
QuickSort(A, q, r);
Hoare-Partition 疑似コード
Hoare-Partition(A,p,r)
x= A[p]
i = p-1
j=r+1
while true
repeat
j=j-1
until A [j] <= x
repeat
i = i +1
until A[i] >= x
if i < l
exchange A[i] with A[j]
else return j
私のコード
public class RunSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] sortNumbers = {4,5,6,2,3,7,2,1};
int[] sorted = new int[sortNumbers.length];
sorted = QuickSort(sortNumbers, 1, sortNumbers.length);
System.out.print(sorted);
}
public static int[] QuickSort(int[] A, int p, int r){
if(p < r){
int q = partition(A, p, r);
QuickSort(A, p, q - 1);
QuickSort(A, q, r);
}
return A;
}
public static int partition(int[] A, int p, int r){
int x = A[p];
int i = p - 1;
int j = r + 1;
int temp;
while(true){
while(A[j] <= x && j != 0){
j--;
}
while(A[i] >= x && i != A.length){
i++;
}
if(i < j){
temp = A[i];
A[i] = A[j];
A[j] = temp;
}else{
return j;
}
}
}
}