1

ソートされていない整数の配列を分割して征服し、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];

誰かがこのアルゴリズムに何か問題があるのを見ることができるなら、私に知らせてください。私は何時間もデバッグしてきました。ありがとう。

4

1 に答える 1

1

6番目の要素の入力1,2,3,20,4,5,6と検索に失敗します。これは、この場合、要素を複数回交換する必要があり、決してそうしないように思われるためです。20 と 6 を交換しますが、その後 i を増やします。したがって、実際に交換する必要があるときに 6 を交換することはありません。6が正解です。どのような値が見つかるかわかりませんが、6 にはなりません。

また、要素がピボットに等しいために、いくつかの問題が発生する可能性があります。そのような要素に対して特別なチェックを追加してみてください。

于 2013-03-08T21:56:27.680 に答える