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

質問

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

回答No.10

amanojaku1

言い回しが変でした。

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

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

回答No.9

amanojaku1

>回答No.8　amanojaku1

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

回答No.8

amanojaku1

バイナリー・ツリー：バランスさせるアルゴリズム

平衡木 - 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

回答No.7

amanojaku1

>処理的にはソートと言うよりは(バイナリー・ツリーの)マージ

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

回答No.6

amanojaku1

>>ソートしないと仮定して、数字の小さい順に順番の番号を割り振るとします、結局これはソートと同じです。

>ソート方法を工夫しましょう(バイナリー・ソート(正式名称ではありません)とか)。

後、バイナリー・ツリーを使うソートもあります(処理的には上記のバイナリー・ソートの方が簡単です)
処理的にはソートと言うよりは(バイナリー・ツリーの)マージ(なのでスピード的には早い)
バイナリー・ツリーのバランスが崩れたら、バランスさせる処理が必要(バランスさせないと効率が悪くなる、バランスさせる処理自体は非常に軽い)
バイナリー・ツリーなので、昇順とか降順とかに並んでいる訳ではないので昇順(降順)にトレースする場合はチョットしたアルゴリズムが必要

回答No.5

amanojaku1

>ソートしないと仮定して、数字の小さい順に順番の番号を割り振るとします、結局これはソートと同じです。

ソート方法を工夫しましょう(バイナリー・ソート(正式名称ではありません)とか)。

回答No.4

amanojaku1

>>中央値をソートせずに求める方法がわかりません

>ソートが必要でのようです。

ソートしないと仮定して、数字の小さい順に順番の番号を割り振るとします、結局これはソートと同じです。

回答No.3

amanojaku1

>中央値をソートせずに求める方法がわかりません

ソートが必要でのようです。

【中学数学】中央値（メジアン）の求め方がわかる3ステップ
http://media.qikeru.me/median/

>バケツソートは分かりますが、データがめっちゃ大きい時とかどうせうるんでしょうか？

ソート方法を工夫しましょう(バイナリー・ソート(正式名称ではありません)とか)。

>クイックソート

クイックソートの最悪時の計算量は O(n2) で、これはバブルソート並みの性能らしいです。

回答No.2

HohoPapa

話がかみ合っているかどうか疑問ですが
以下しか思いつきません。

◆母集団の数が奇数個の時

例えば9個の場合
母集団の中で、自身よりも小さい値の数が４個以下
かつ、
母集団の中で、自身よりも大きな値の数が４個以下
という条件の値が見つかるまで1つ目の値から順番に総当たりする。

◆母集団の数が偶数個の時

例えば10個の場合

母集団の中で、自身よりも小さい値の数が４個以下
かつ、
母集団の中で、自身よりも大きな値の数が５個以下
という条件の値が見つかるまで1つ目の値から順番に総当たりする。
更に
母集団の中で、自身よりも小さい値の数が５個以下
かつ、
母集団の中で、自身よりも大きな値の数が４個以下
という条件の値が見つかるまで1つ目の値から順番に総当たりする。

その後この２つの値の平均を求める

回答No.1

foomufoomu

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