Quickselectの実装が機能しない

Question

配列内のn個の最小項目を決定するコードを記述しようとしています。私はこれで苦労していることは悲しいことです。今日の私の大学の教科書のアルゴリズムに基づいて、これは正しいと思われる。しかし、私はスタックオーバーフローの例外を与えるので、明らかに私は間違って何かをしています。

私のアプローチがある：

この位置で整数を使用

（よりむしろオーバーフローを防止するために、+エンド/ 2開始）開始+（エンド開始）/ 2になるようにピボットを設定

1. 私は反復
にすべてを比較すると、物事がソートされているように、このピボットの周りのすべてを入れ替えるピボット（ピボットにソートされた相対的な）
3. n個の場合==ピボットであることを、私は、私はそうでない
4. を行っていますだと思います私は4つのsmallesをしたい場合t要素とピボットは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); 
    } 
} 

編集：あなたは、有効な質問をdownvoteするつもりなら、少なくとも、なぜわざわざコメントしてください。

Answer 1

私がした最初のことは、どのようにピボット/パーティションポイントを取得するのかということでした。 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); 
    } 
} 

Answer 2

この問題が解決しないだろうが、あなたのコードにはいくつかの問題があります：あなたは私<終了とjをチェックしない場合は

• >あなたwhilesに開始するには、あなたがのうちに実行することがあり一部のケースでは境界
• ピボットをサブアレイの中央にするように選択しますが、分割中に位置が変わらないことは何も証明されていません。次に、古いピボットポジションでk ==ピボットを確認します。これは明らかに機能しません。

これはちょっと役立ちます。