K 번째 가장 작은 요소 알고리즘

Question

k 번째 가장 작은 요소를 찾기 위해 정렬되지 않은 정수 배열을 나누고 정복하는 알고리즘을 작성했습니다. 프로그램을 테스트 할 때 몇 가지 결과가 잘못되었습니다. 코드는 다음과 같습니다.

public class kthsmallest { 

public static final int MaxSize = 500; 

public static int find_kth_smallest(int[] A, int n, int k) 
{ 
     return quicksort(A, n, k, 0, n-1); 
} 

public static int quicksort(int[] A, int n, int k, int low, int high){ 
int i = low; 
int j = high; 
int position = low + (high-low)/2; 
int pivot = A[position]; 

while (i <= j){ 
    while(A[i] < pivot) 
     i++; 

    while(A[j] > pivot) 
     j--; 

    if (i <= j){ 
     int temp = A[i]; 
     A[i] =A[j]; 
     A[j] = temp; 
     i++; 
     j--; 
    } 
} 

// 
if (position + 1 > k){ 
    return quicksort(A, n, k, low, position-1); 
} else if (position + 1 < k){ 
    return quicksort(A, n, k, position+1, high); 
} else 
    return A[position]; 

누구든지이 알고리즘에 문제가 있다고 생각되면 알려 주시기 바랍니다. 나는 몇 시간 동안 디버깅을 해왔다. 감사.

Answer 1

입력 1,2,3,20,4,5,6에 대해 잘못되어 6 번째 요소를 검색합니다. 그 이유는이 경우에 한 번 이상 요소를 교환해야하므로 절대 그렇게하지 않는 것 같습니다. 당신은 20과 6을 바꿀 것입니다.하지만 그 후에는 당신이 늘릴 것이고, 따라서 당신이 실제로해야하는 동안 나는 다시 6을 바꿀 수 없을 것입니다. 6 정답입니다. 어떤 값을 찾을 지 확신 할 수 없지만 6이되지 않습니다.

피벗과 동일한 요소로 인해 여러 가지 문제가 발생할 수 있습니다. 이러한 요소에 대한 특별 검사를 추가하십시오.