問題タブ [quickselect]

「ランダム化されたピボット」メソッドを使用して、指定された配列の中から K 番目の最小要素を見つけようとしました。
[コード]

しかし、結果は不安定で、正しい場合もあれば間違っている場合もあります。メソッド
の 5 行目を見てください。 これを に変更すると、結果は常に正しいです。これのどこが悪いのか本当にわかりません。 findKthMin_RanP_Helper
int split = partition(givenArray, start, end, rand);int split = partition(givenArray, start, end, end);

そして、次のfindKthMin_RanP_Helperように変更する必要があります。

以下を実行するための効率的なアルゴリズムを探しています: N 個の項目の配列が与えられた場合、項目が M 個の等しいグループになるように並べ替えます。各グループは並べ替えられていませんが、グループは互いに並べ替えられています (すべての要素)あるグループの要素は、次のグループのどの要素よりも少ない)。

最も簡単な方法は、配列全体をソートすることです。しかし、特にグループの数が項目の総数よりもはるかに少ない場合 (たとえば、100 万の項目を 5 つのグループに分類する場合) は非効率的です。

現在、配列を2つのソートされていないグループにソートし、それをM-1回適用するquickselectアルゴリズム(具体的にはFloyd-Rivestのバリエーション)を使用することに決めました。大幅な改善は、クイック選択に分割統治法を適用することです。最初に配列を 2 つのグループにソートし、次に各半分をソートするというように、M 個のグループが得られるまで続けます。順序付けられていない部分的な並べ替えの問題の一種の一般化。

しかし、私は、この問題に対するより単純で効率的なアプローチがあるかもしれないという直感を持っています。足りないものはありますか？何か案は？これは、 RBush JavaScript ライブラリ(効率的な R* ツリーの実装)での一括挿入のパフォーマンスを向上させるために必要です。

配列の中央値を返すアルゴリズムを実装する必要があります。そこで、これには効率的であると思われる Quickselect を実装することにしました。3 分割には、Quicksort で使用されているものと同じ分割アルゴリズムを使用できることがわかりました。

私の講義ノート (C コード) で報告されているパーティション アルゴリズムは次のとおりです。

ここで、配列が a = [40, 20, 100, 60, 80] で、ピボットとして 80 を選択すると、結果は a = [40, 20, 80 , 60, 100] になりますが、右側のパーティションの値がすべて > 80 ではないことがわかります (60 あります)。他の数値を選択すると、アルゴリズムは適切に機能します。

このアルゴリズムは間違っていますか？

事前に助けてくれてありがとう！

ランダムに生成された数値を持つ配列にクイック選択アルゴリズムを実装しようとしています。アルゴリズムをコードで記述した後、配列を最小から最大にソートせず、k 番目に小さい要素を見つけることもできません。私が得た助けに感謝します。ありがとうございました。

クイック選択のために最後の要素に対してランダムなピボットを選択する意味はありますか?

常に最後の要素をピボットとして選択することで、必要な要素を見つけることができます。ランタイムに影響しますか。

線形選択 (中央値アルゴリズムの中央値) の再帰方程式は次のとおりであることを知っています。

しかし、これらの用語はどこから来たのでしょうか? 私は理解しようとしてきましたが、私は非常に混乱しています。誰でも光を当てることができますか？