クイックソートの実装のためのjavaのメディアンの中央値を見つける方法

Question

私は宿題のためのクイックソートアルゴリズムを一晩中適切に実装していて、数時間の検索をした後、パーティショニング。だから、私はアルゴリズムのどの部分がひどく壊れているのかわからない巨大なロードブロッキングに悩まされています。オンラインのアルゴリズムはすべて擬似コードなので（パーティションの説明が曖昧です）、私は私の実装に対してチェックする。だから私のフランケンシュタインのコードはmedianのピボット選択の中央値がjavaのクイックソートでどのように働くかという文書の後に文書を読んだ後です。ここで

は、私がこれまでにも、リモートで有用見つけた、と彼らはすべてのアルゴリズムを動作させるための部品で痛々しいほど漠然としている唯一の情報源は、意図的にそのように多くの時間検索を過ごした後と思われる、次のとおりです。

http://mitpress.mit.edu/algorithms/solutions/chap9-solutions.pdf

http://www.cs.umd.edu/~meesh/351/mount/lectures/lect9-medians-selection.pdf

*のhttp：//www.ics.uci.edu/~eppstein/161/960130.html

*のhttp：//en.wikipedia.org/wiki/Selection_algorithm

ここで

は私のクイックソートアルゴリズムです：

{Removed Code} 

そして、ここに私の選択方法で、私は中央値を選択して、中央値の中央値どのように恐ろしくめちゃめちゃ部分があると思いますが、私は、オンラインで何かを見つけることができませんでした分割に私を導くために：私がいた何かがあった場合、私は私の定期的なクイックソートの分割方法を使用しますが、ピボットがパラメータとして与えられているので、少しそれを変更し、私のパーティションのためにも

{Removed Code} 

、私は知りませんオンラインのすべてのソースがこの分野でも漠然としているので、ここで

{Removed Code} 

は、念のために、5のグループをソートするための私の挿入ソートです：

{Removed Code} 

私がしてきたように私はめちゃくちゃアルゴリズムのどの部分にどれ洞察力が非常に高く評価されるだろう何が間違っているのかを見つけようと壁に向かって頭を打つ。私のJUnitテストは、[1..100]のプリセットされた配列に対して期待される結果が50である中央値を選択できないため、選択アルゴリズムに大きな間違いがありますが、私のアルゴリズムは常に54を吐き出します。

Answer 1

Whereその横の要素を選択している5要素の「サブセット」から中央値を選択する必要があります。中間値にはインデックス2がありますが、インデックス3を選択しています。あなたが必要とする：

int median = subset[2]; // Or sslength/2 if you don't like hardcoded values 

ところで、[1..100]の「中央値の中央値は、」50は20で5グリッド内の数字を書くない、48または53のようになります。値の中央の行（3,8,13、...）は「サブセット」の中央値です。