0
다음 "qsort"구현은 "Foundations of Algorithms"라는 책의 내용이므로 올바른 것으로 판단됩니다. 아래 자바 구현입니다. 작동하지 않습니다. 문제는 파티션을 임의로 선택하면 생성 된 파티션이 올바르지 않다는 것입니다. 나는 누군가가 내가 뭘 잘못 말해 줄 수 바라고 :무작위 파티션을 사용하는 QSort
밥
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");
}
}
디버거에 익숙해야합니다. –
부정확하게 수행하는 작업의 예는 사용자가 직면 한 문제를 이해하는 데 도움이됩니다. – Daniel
힌트 : 인덱스 변수를 증가시킬 때주의하십시오. – samgak