みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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

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

投稿日時 - 2018-04-26 21:47:19

QNo.9492584

困ってます

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(10)

ANo.10

言い回しが変でした。

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

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

投稿日時 - 2018-05-07 15:41:52

ANo.9

>回答No.8 amanojaku1

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

投稿日時 - 2018-05-06 15:25:07

ANo.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

投稿日時 - 2018-05-05 20:02:53

ANo.7

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

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

投稿日時 - 2018-05-05 19:20:16

ANo.6

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

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

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

投稿日時 - 2018-05-05 19:13:55

ANo.5

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

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

投稿日時 - 2018-05-05 18:25:22

ANo.4

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

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

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

投稿日時 - 2018-05-05 18:21:13

ANo.3

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

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

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

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

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

>クイックソート

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

投稿日時 - 2018-05-04 16:07:41

ANo.2

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

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

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


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

例えば10個の場合

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

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

投稿日時 - 2018-04-28 12:11:53

ANo.1

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

投稿日時 - 2018-04-26 23:15:41

あなたにオススメの質問