問題タブ [quickselect]

マルチセットを介して O(n) の k 番目の要素を検索することは可能ですか (値は繰り返すことができます)?

クイック選択のアイデアを理解している限り、ピボットを使用して入力を分割する必要があるためです。次に、再帰検索用に選択する2つの配列があります。これは、検索しているインデックス要素と、たとえば両方の配列のサイズによって異なります。

1 7 8 5 3 2 4

ピボットが 4 だとしましょう。私は 2 番目に大きな要素を探しています。したがって、パーティショニング後、次のような順序になる可能性があります

1 3 2 4 7 8 5

右側のサブ配列は 3 つの要素で構成されているため、正しい場合は右側の配列で 2 番目に大きいものを見つけようとしますか?

しかし、ピボットとして 8 を使用すると、次のような結果が得られる可能性があります。

1 3 2 7 5 4 8

したがって、左のテーブル内で最大の要素を見つけようとします（おそらく線形ですが、一般的には左のサブ配列を取得して要素を検索します-（|右のサブ配列サイズ| + 1））

しかし、マルチセットはどうですか? 私が配列を持っているとしましょう：

4 5 6 7 7 7 4 3 2 1

そして、私のピボットは 6 番目に大きい要素を検索することです。

4 5 3 2 4 1 6 7 7 7

したがって、上記のアプローチを使用すると、右側のサブ配列で再帰を実行しようとしますが、3 番目に大きい値は左側にある 5 であることが明らかですか?

私が思いついた唯一の解決策は、BST、Setなどのデータ構造を使用して、O(nlogn)で繰り返しを除外することです。次に、O(n) クイック選択を使用します。しかし、全体としては非線形のアプローチになりましたが、これを線形にすることはできますか?

追加の質問もありますが、メモリの割り当てができない場合はどうすればよいですか? そして、私ができることは、ローカル ints + スタック再帰のみを使用することです。問題は O(n) で解決できますか? O(nlogn) は、並べ替え + 線形の「カウントを通過する」ことで実行できるためです。

ここで説明するクイックセレクトを実装する小さなPythonコードがあります。

randrangeエラーが発生しているようです。何かがおかしいですか？

編集：random.choiceの代わりに実装されrandom.randintます。上記のコードは正常に機能しているようです。UserBlenderに感謝します。

よろしければ宿題のお手伝いをさせていただきます。基本的には、値の配列に対してクイックセレクトを実行するという考え方ですが、テンプレートが提供されており、提供されているもので関数を機能させる方法がわからないようです。

問題は、値が正しく配置されないか、配置されている場合、同じ値が入力されるたびに値が変更されることです。

これが私が使用している関数です。コードの後に​​/**/を使用して記述したコードを示し、他の行は私に提供されたテンプレートの一部です。

「test.txt」ファイルには次の値が含まれています。

これについての助けをいただければ幸いです。私の教授はこれがどのように機能するかをまったく説明していませんでした。オンラインで見つけた他の例は私の質問に答えません。私はこれを実装するさまざまな方法をいじくり回して何時間も費やしてきましたが、現時点ではまったくわかりません。ありがとう

編集：変更されたため、直接実装およびコンパイルできるようになりました。私が使用しているライブラリも追加しました

そのため、ベクトル内の中央値を見つけるために C++ でクイック選択アルゴリズムを実装しようとしていますが、リストを適切に部分的にソートしておらず、正しい中央値も返していません。

エラーがどこにあるかを見つけることができないようです。私はこのアルゴリズムを初めて使用し、それを実装しようとするのは初めてです。以下に私のコードを含めましたので、私よりも知識のある人が何がうまくいかないのかについて何か考えを持っているなら、私はあなたの意見に非常に感謝しています.

さて、私は一般的なクイック選択関数を開発しました。これは、リストの中央値を見つけるために使用されます。

では、ピボットが毎回リストの最初の項目から開始された場合、プログラムはどのように異なる動作をするでしょうか。センターにしないといけないの？また、関数の経過時間を見つけるために、どこで time.clock() を開始する必要がありますか。ここにコードがあります

いくつかのことに取り組んでいると、理解できないという奇妙な問題に遭遇しました。10,000 個の値を持つリストを 2 つの方法で並べ替えています。1 つはクイック選択を使用し、もう 1 つは挿入並べ替えを使用します。これの目標は、中央値を見つけることであり、その中央値を使用して、中央値とすべての値の間の合計距離を見つける必要があります。中央値の計算は完全に正常に機能しますが、合計の計算では、理解できない理由で異なる値が返されます。合計を計算する関数への入力は、リストと中央値です。中央値は両方のプログラム間で同じままであり、リストの値も同じですが、リストの 1 つが並べ替えられ、もう 1 つのリストは並べ替えられていません。

これが合計を計算するために使用しているものです（これのフォーマットは問題なく、ここにコピーするだけです）...

あるリストがソートされていて、別のリストがソートされていない場合、なぜ劇的に異なる値が得られるのでしょうか? 参考までに、挿入ソートを使用した場合の距離は 49846.0 ですが、クイック選択を使用した場合の距離は 29982 です。

そのため、クイック選択機能のコードを開発しましたが、中央値を出力していないようです。ファイル名のメイン関数プロンプトがあり、そのtxtファイルをインポートし、数字のリストに分割します。これがtxtファイルです。

リストにインポートされます：

クイックセレクト関数を実行すると、経過時間が1.9083486328125e-06のように毎回変化する奇数であることが出力されます...最初に、これはミリ秒単位でどのような時間の値ですか? 関数が実行されてピボットが返されると、次のように吐き出されます。

誰かがなぜそれが機能しないのか教えてもらえますか? これはコードです：