-1

配列内の n 個の最小項目を判別するコードを作成しようとしています。私がこれに苦労しているのは悲しいことです。昔の私の大学の教科書のアルゴリズムに基づくと、これは正しいように見えます。ただし、スタックオーバーフロー例外が発生するため、明らかに何か間違っています。

私のアプローチは次のとおりです。

  1. ピボットを start + (end-start) / 2 に設定します (オーバーフローを防ぐために start+end/2 ではなく)
  2. この場所の整数を使用して、すべてを比較するピボットにします
  3. このピボットの周りのすべてを繰り返し交換して、物事がソートされるようにします（ピボットを基準にしてソートされます）
  4. n == ピボットの場合、完了したと思います
  5. それ以外の場合、たとえば 4 つの最小要素が必要でピボットが 3 の場合、右側 (または 2 番目に小さい要素が必要な場合は左側) を見る必要があります。

-

public static void main(String[] args) {
    int[] elements = {30, 50, 20, 10};
    quickSelect(elements, 3);
}

private static int quickSelect(int[] elements2, int k) {
    return quickSelect(elements2, k, 0, elements2.length - 1);
}

private static int quickSelect(int[] elements, int k, int start, int end) {
    int pivot = start + (end - start) / 2;
    int midpoint = elements[pivot];
    int i = start, j = end;

    while (i < j) {
        while (elements[i] < midpoint) {
            i++;
        }

        while (elements[j] > midpoint) {
            j--;
        }

        if (i <= j) {
            int temp = elements[i];
            elements[i] = elements[j];
            elements[j] = temp;
            i++;
            j--;
        }
    }
    // Guessing something's wrong here
    if (k == pivot) {
        System.out.println(elements[pivot]);
        return pivot;
    } else if (k < pivot) {
        return quickSelect(elements, k, start, pivot - 1);
    } else {
        return quickSelect(elements, k, pivot + 1, end);
    }
}

編集：有効な質問に反対票を投じる場合は、少なくとも理由をコメントしてください。

4

2 に答える 2

0

よし、最初にしたことは、ピボット/パーティション ポイントを取得する方法を作り直すことでした。T. Claverie が指摘したように、欠点は、分割フェーズ中に要素の位置が変化するため、私が使用しているピボットが技術的にピボットではないことです。

以下のように、実際にパーティショニング コードを独自のメソッドに書き直しました。これは少し異なります。

最初の要素 (開始時) をピボットとして選択し、このピボットよりも少ないアイテムでこの前に「セクション」を作成します。次に、ピボットの値を値のセクション < ピボットの最後の項目と交換します。その最終的なインデックスをピボットのポイントとして返します。

これはさらにクリーンアップできます (別のスワップ メソッドを作成します)。

private static int getPivot(int[] elements, int start, int end) {
    int pivot = start;
    int lessThan = start;

    for (int i = start; i <= end; i++) {
        int currentElement = elements[i];
        if (currentElement < elements[pivot]) {
            lessThan++;
            int tmp = elements[lessThan];
            elements[lessThan] = elements[i];
            elements[i] = tmp;
        }
    }
    int tmp = elements[lessThan];
    elements[lessThan] = elements[pivot];
    elements[pivot] = tmp;

    return lessThan;
}

これを呼び出すルーチンは次のとおりです。

private static int quickSelect(int[] elements, int k, int start, int end) {

    int pivot = getPivot(elements, start, end);

    if (k == (pivot - start + 1)) {
        System.out.println(elements[pivot]);
        return pivot;
    } else if (k < (pivot - start + 1)) {
        return quickSelect(elements, k, start, pivot - 1);
    } else {
        return quickSelect(elements, k - (pivot - start + 1), pivot + 1, end);
    }
}
于 2016-05-15T08:22:08.477 に答える