問題タブ [median-of-medians]

中央値アルゴリズムの中央値を使用したクイックソートに取り組んでいます。通常、選択ソートを使用して、5 つの要素のサブ配列の中央値を取得します。ただし、サブアレイが数千ある場合は、千の中央値の中央値を見つける必要があることを意味します。最適ではないため、選択ソートを使用してその中央値を見つけることはできないと思います。

質問：

誰かがその中央値を見つけるためのより良い方法を提案できますか? 前もって感謝します。

クイックソートパーティショニングの改善を実装しながら、Tukey の ninther を使用してピボットを見つけようとしました (QuickX.java での sedgewick の実装からほとんどすべてを借用しています)。

以下のコードでは、整数の配列がシャッフルされるたびに異なる結果が得られます。

タッキーの第九は、同じデータセットの異なるシャッフルに対して異なる値を与えるでしょうか? 手で中央値の中央値を見つけようとしたとき、コード内の上記の計算が正しいことがわかりました..つまり、同じデータセットがデータセットの中央値とは異なり、異なる結果をもたらすことを意味します.これは適切な動作ですか? 統計学に詳しい方コメントいただけませんか？

配列の要素を 3 つのグループに分割する必要があります。これは、配列をソートせずに行う必要があります。例を考えてみましょう

120 個の並べ替えられていない値があるため、最小の 40 個の値を最初のグループに、次の 40 個を 2 番目のグループに、最大の 40 個を 3 番目のグループにする必要があります。

中央値アプローチの中央値を考えていましたが、それを私の問題に適用できませんでした。親切にアルゴリズムを提案してください。

Median of Medians アルゴリズムで「5」がどこから来たのかを理解しようとしてきましたが、それがどのように導き出され、なぜ最適なのかについての簡単な説明が見つからないようです。

たとえば、なぜ 7 と言うのが実行可能なオプションではないのでしょうか?

5 の唯一の利点は、中央の両側に 2 つのアイテムがあり、5 つのアイテムの並べ替えが 3 つ以下のスワップの単純なケースであることです。

quickselectとして知られているアルゴリズムの github でこのコードを見つけましたorder-statistics。このコードは正常に動作します。

medianOf3最初、中間、最後のインデックスをソート順に並べる方法がわかりません。しかし、実際には、メソッドを呼び出した後に配列を出力するときはそうではありませんmedianof3。の最後の呼び出しを除いて、このメソッドが何をしているのかについては、このメソッドに従うことができますswap(list, centerIndex, rightIndex - 1);。誰かがなぜこれが呼び出されたのか説明できますか?

分散コンピューティングについて学ぼうとしていたところ、多数の数値セットの中央値を見つけるという問題に遭遇しました。

メモリ (サイズ N) に収まらない大きな数のセット (要素の数が N*K であるとします) があるとします。このデータの中央値をどのように見つけますか? メモリ上で実行される操作は独立していると仮定します。つまり、それぞれが最大で N 個の要素を処理できる K 台のマシンがあると見なすことができます。

中央値の中央値がこの目的に使用できると思いました。一度に N 個の数値をメモリにロードできます。そのセットの中央値を時間で見つけてO(logN)保存します。

次に、これらの K 個の中央値をすべて保存して、中央値の中央値を見つけます。繰り返しO(logK)ますが、これまでのところ複雑さはありませんO(K*logN + logK)。

しかし、この中央値の中央値は、おおよその中央値にすぎません。最適なパフォーマンスを得るには、これをピボットとして使用するのが最適だと思いますが、そのためには、すべての N*K 数値をメモリに収める必要があります。

適切な近似ピボットが得られたので、セットの実際の中央値を見つけるにはどうすればよいでしょうか?

ソートされていないリストでおおよその中央値を見つけたい、2つのアルゴリズムを知っている

アルゴリズム 1 - クイックセレクト

アルゴリズム 2 - 中央値の中央値

私のプロジェクトでは、最悪の場合 O(n^2) かかるため、クイック選択を使用できません。中央値の中央値について聞いたことがありますが、私の同僚は、一定の係数を持つ O(n) が必要であることを示唆しています。中央値の中央値に関連付けられている定数要因は何ですか?また、中央値の中央値が9要素の疑似中央値を使用しないのはなぜですか?
または、線形時間 O(n) でおおよその中央値を見つけるための他のアルゴリズムですか?