問題タブ [quickselect]

配列内の th 要素を取得するためにクイック選択アルゴリズムを実装していkますが、解決方法がわからない場所で立ち往生しています。動作しない私のコードは次のとおりです。

確かに、これらの行を削除すると:

クイックソートになり、正常に動作します。そして、それが機能しない理由を理解しています。これは、上記の条件で戻ったときに、0 から k まで取得している配列がソートされていない可能性があるためです。しかし、配列内の最初の k 個の要素のみを並べ替えて残りを除外する適切な条件を見つけることができないため、余分な作業を行う必要はありません。私はオンラインでいくつかの実装を見て、上記に時間を費やしましたが、それを理解することができなかったので、助けを求めてください.

私はPythonが初めてで、コードを書く練習をしていますが、いくつかの問題があります。

K 個の最大要素を抽出できるQuickSelectに基づくアルゴリズムを実装しようとしています。

そのため、アルゴリズムを実装し、QuickSelectそれを使用して配列 A の K 番目に大きい要素を見つける前に、関数を使用して配列 A をスキャンし、で見つかった K 番目の要素以上のK 要素k_largest_quickselect(A, K)を収集します。最後に、集めた要素を並べ替えます。QuickSelect

これは私の実装のコードです:

アルゴリズムをテストしてみました

この結果を得る

ご覧のとおり、関数k_largest_quickselect(A = a, K = 3)を使用しても、配列の最大 3 つの要素を取得できませんでした。

この問題を解決するのを手伝ってくれませんか? どうもありがとうございました！