締切済み

中央値をソートせずに求める

2018/04/26 21:47

中央値をソートせずに求める方法がわかりませんオーダーはO(N)以下ですバケツソートは分かりますが、データがめっちゃ大きい時とかどうせうるんでしょうか？

komattakayo
お礼率0% (0/49)

C・C++・C#
回答数10
ありがとう数0

みんなの回答 （10）
専門家の回答

みんなの回答

amanojaku1
ベストアンサー率54% (265/488)

2018/05/07 15:41 回答No.10

言い回しが変でした。 >結果的にはソートになってますが、(バイナリー・ツリーの)マージなので「中央値をソートせずに求める」に一番即していると思います(当然、プログラム的には面倒です)。ソートが必要なので、結果的にソートになりますが、プログラムの処理としては(バイナリー・ツリーの)マージなので「中央値をソートせずに求める」に一番即していると思います(当然、プログラム的には面倒です)。

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/06 15:25 回答No.9

>回答No.8　amanojaku1 このようにバイナリー・ツリーは(プログラム的に)少々面倒なので、普通にソートした方が(プログラム的に)簡単です(ソート方法を工夫しましょう)。

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/05 20:02 回答No.8

バイナリー・ツリー：バランスさせるアルゴリズム平衡木 - f-server http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg11-%E5%B9%B3%E8%A1%A1%E6%9C%A8.pdf バイナリー・ツリー：ノードを削除するアルゴリズム [PDF]二分探索木 - f-server http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg10-%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8.pdf

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/05 19:20 回答No.7

>処理的にはソートと言うよりは(バイナリー・ツリーの)マージ結果的にはソートになってますが、(バイナリー・ツリーの)マージなので「中央値をソートせずに求める」に一番即していると思います(当然、プログラム的には面倒です)。

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/05 19:13 回答No.6

>>ソートしないと仮定して、数字の小さい順に順番の番号を割り振るとします、結局これはソートと同じです。 >ソート方法を工夫しましょう(バイナリー・ソート(正式名称ではありません)とか)。後、バイナリー・ツリーを使うソートもあります(処理的には上記のバイナリー・ソートの方が簡単です) 処理的にはソートと言うよりは(バイナリー・ツリーの)マージ(なのでスピード的には早い) バイナリー・ツリーのバランスが崩れたら、バランスさせる処理が必要(バランスさせないと効率が悪くなる、バランスさせる処理自体は非常に軽い) バイナリー・ツリーなので、昇順とか降順とかに並んでいる訳ではないので昇順(降順)にトレースする場合はチョットしたアルゴリズムが必要

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/05 18:25 回答No.5

>ソートしないと仮定して、数字の小さい順に順番の番号を割り振るとします、結局これはソートと同じです。ソート方法を工夫しましょう(バイナリー・ソート(正式名称ではありません)とか)。

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/05 18:21 回答No.4

>>中央値をソートせずに求める方法がわかりません >ソートが必要でのようです。ソートしないと仮定して、数字の小さい順に順番の番号を割り振るとします、結局これはソートと同じです。

ログインすると、全ての回答が全文表示されます。

amanojaku1
ベストアンサー率54% (265/488)

2018/05/04 16:07 回答No.3

>中央値をソートせずに求める方法がわかりませんソートが必要でのようです。【中学数学】中央値（メジアン）の求め方がわかる3ステップ http://media.qikeru.me/median/ >バケツソートは分かりますが、データがめっちゃ大きい時とかどうせうるんでしょうか？ソート方法を工夫しましょう(バイナリー・ソート(正式名称ではありません)とか)。 >クイックソートクイックソートの最悪時の計算量は O(n2) で、これはバブルソート並みの性能らしいです。

ログインすると、全ての回答が全文表示されます。

HohoPapa
ベストアンサー率65% (455/693)

2018/04/28 12:11 回答No.2

話がかみ合っているかどうか疑問ですが以下しか思いつきません。 ◆母集団の数が奇数個の時例えば9個の場合母集団の中で、自身よりも小さい値の数が４個以下かつ、母集団の中で、自身よりも大きな値の数が４個以下という条件の値が見つかるまで1つ目の値から順番に総当たりする。 ◆母集団の数が偶数個の時例えば10個の場合母集団の中で、自身よりも小さい値の数が４個以下かつ、母集団の中で、自身よりも大きな値の数が５個以下という条件の値が見つかるまで1つ目の値から順番に総当たりする。更に母集団の中で、自身よりも小さい値の数が５個以下かつ、母集団の中で、自身よりも大きな値の数が４個以下という条件の値が見つかるまで1つ目の値から順番に総当たりする。その後この２つの値の平均を求める

ログインすると、全ての回答が全文表示されます。

foomufoomu
ベストアンサー率36% (1018/2761)

2018/04/26 23:15 回答No.1

データの値範囲が広かったりすると、じつは低速なバケツソートを使うという条件なら、１．始めは荒い分割の（少ない数の）バケツを用意し、１回目のバケツソートを行う。２．各バケツ内のデータ個数を数えて、n/2番目のデータが含まれるバケツを取り出す。３．その１バケツを、また１～２の方法でバケツソートする。４．バケツのデータが1/2番目のデータ1個だけになったら、処理を終わる。これでは、「ソートせずに」にはなっていませんが、「全部をソートせずに」という事にはなっている？？？バケツソートと言うよりは、クイックソート（オーダーはO(n*log(n)）ですが。

ログインすると、全ての回答が全文表示されます。