• 締切済み

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

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

みんなの回答

回答No.10

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

回答No.9

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

回答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

回答No.7

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

回答No.6

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

回答No.5

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

回答No.4

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

回答No.3

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

  • HohoPapa
  • ベストアンサー率65% (454/691)
回答No.2

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

  • foomufoomu
  • ベストアンサー率36% (1018/2761)
回答No.1

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • phpでのソートについて

    phpのソートについて教えてください。 以下のようなカンマ区切りのログファイルlog.txtがあるとしまして、 100,200,a,b,c, 300,100,d,e,f, 500,60,g,h,i, 50,300,j,k,l, 1000,60,m,n,o, このデータから １番目のデータ（数値）が２番目のデータ（数値）より大きいデーターのみを対象にして ※つまりは以下のみ対象 300,100,d,e,f, 500,60,g,h,i, 1000,60,m,n,o, ここから１番目のデータ（数値）から２番目のデータ（数値）を引いた数が大きい順に ソートしてファイルに保存させたいのですが、 200,d,e,f,（300-100なので200） 440,g,h,i,（500-60なので440） 940,m,n,o,（1000-60なので940） ↓ ※最終的にこの順番で新しいログファイルnewlog.txtへ保存させたい 940,m,n,o, 440,g,h,i, 200,d,e,f, これらの処理を効率よく１度で行う方法はございますでしょうか。 わかりにくい説明で申し訳ありません。 お忙しい中恐縮ですがご教授いただけましたら幸いです。 何卒宜しくお願い致します。

    • ベストアンサー
    • PHP
  • 社員IDのソート

    社員IDの桁が混在しています。 社員IDでorder byすると 0001 0011 100 1200 123 1234 321 となります。これを 100 123 321 0001 0011 1200 1234 と桁数別にソートしたいと考えています。 ちなみにVARCHARです。 order by 以下うまくソートする方法が知りたいです。 お願いします。

  • ソートの計算量などについて

    こんにちは ソートに関することの質問です。 １．バブルソートの計算量を出す式ですが Ｏ(n^2)=Ｏ(n-1)*Ｏ(n/2)*Ｏ(1)=Ｏ(n)*Ｏ(n)=Ｏ(n^2) で合っていますでしょうか？ ２．クイックソートの（平均）計算量が ｎlog n(底は２)になるのは、なぜなのかを わかりやすく教えて下さい。（できれば式も） ３．クイックソートが最も高速に実行されるのは、ピボットの要素が真中にある場合で、反対に最も効率が悪いのはピボットが端にある場合ですが、この理由をやさしい言葉で教えて下さい。 どなたか教えて下さい。 よろしくお願いします

  • ヒープソートは２重ソートできない？

    　ソートに関して詳しい方、相談にのっていただけたらと思います。 　ＣＧＩを使ってヒープソートするロジックを組みました。 　そのルーチンはただ単項データをソートするだけでなく、たとえば、配列変数 n1 と 配列変数 n2 にそれぞれデータが入っていたとき、n1 をソートすると、それに連動して n2 の中身も一緒にソートされます。 　言うならば、バラバラに並んだビデオテープを番号順に並べ替えると、一緒にタイトルも並べ変わる感じです。 　ところが、配列 n1 をソートしていてたまに同じ数字が入っていることがあります。そういうときは n2 の順にしたいのです。 　そこで、先に n2 をソートしてから n1 をソートするといいのではと考え、そのようにプログラムを組んでみました。 　ところが実際には、n1 をソートした瞬間に、せっかく並べ替えた n2 の内容がバラバラになってしまうのです。 　「n1 の内容が同じ場合は n2 を昇順に並べる」という処理を記述していても、実際には n2 の内容はバラバラです。 　これはヒープソートを使用している限り仕方のないことなのでしょうか。あるいは何らかの解決方法を知っている方、よろしくお願いします。

  • クイックソートの比較回数について

    中央値をピボットとするクイックソートで、入力データ数が１０２４で昇順データの場合はＯ(nlogn)の関係より10240回の比較回数が得られる、というのは合っているでしょうか？ ご回答お願い致します。

  • ソートの作りかた！

    ソートの作りかた！ ソートを作ろうと思うのですが作り方がわかりません＞＜ 色々な検索エンジンで調べたのですが 作る方法が乗っているのが見つかりませんでした！ どなたか作り方を教えてくださると嬉しいです。 こんな感じのが作ってみたいです↓ http://korason.o-oku.jp/dsort.html

  • Excel2010 VBA sortについて

    現在Excel2010VBAを使って、化学のデータからスペクトルを出すようなプログラムを考えております。 データは以下のような形です。 温度 1500 1500 1500 1400 1400 1400 時間 5 10 20 5 　10 　20 電流 1 3 7 11 　12 13 このようなデータをまず、1行のデータの順番に並べてから、2行のデータ順に並べ替えたいと思っています。 しかし、Sortを用いたところ、実行時エラー1004RangeクラスのSortエラーが検出されてしまいます。 そこで、SortSpecialにすると、このエラーは検出されず、マクロは回るものの思った通りに整列されません。 Sheets("Rawdata").Activate Columns("A:BE").Sort Key1 = Range("A7") Order1 = xlAscending Key2 = Range("A10") Order2 = xlAscending Header = xlGuess Orientation = xlLeftToRight Excelの整列を使えばできてしまうことなのですが、VBAを用いてはできないのでしょうか？ ExcelVBAを用いて、「行のデータ」基準にして「列を並べ替える」ことは可能なのでしょうか？ どなたかご教授ください。 よろしくお願いいたします。

  • NULL値を含むソート

    MySQL4.0.20を使っています。 以下のようなデータをソートすると NULLが先に表示されます。 これをNULLを最後にして、数値のソートをかけたいです。何か解決策はありますか？２回に分ける方法しかないのでしょうか？ nullと非null ◆元データ A --- 5 NULL 2 NULL 3 1 select A from xxx order by A asc; ●望まない結果 A --- NULL NULL 1 2 3 5 ●望む結果 A --- 1 2 3 5 NULL NULL ※話は変わりますが、4.1で日本語EUCの文字化けバグは直っているのでしょうか？

    • ベストアンサー
    • MySQL
  • シェルソートの計算量を求める方法について

    シェルソートで最悪の場合の計算量を求めたいです。 オーダーがnの二乗になるは知っていますが、その求め方、式がしりたいです。 要素数をN、感覚を４、２、１でお願いします。 考え方として各間隔のときのソート結果を無視して、各間隔時に単純挿入ソートと同様にして計算するのでしょうか？ それとも、各間隔でのソート結果を考慮するべきなのでしょうか？ できれば計算式と考え方、両方教えていただければありがたいです。 回答よろしくお願いします。

  • 中央値の大小関係について

    中央値の大小関係について n個のデータがあるとき、データの中央値 m を以下のように定義します。 中央値＝ 小さい方から (n+1)/2 個目のデータ 〔nは奇数〕 　 小さい方から n/2 個目のデータと n/2+1 個目のデータの平均　〔nは偶数〕 次にn個のデータを n1個とn2個のデータに分割(n1+n2=n)し、 n1個のデータの中央値を m1 n2個のデータの中央値を m2 とします。 このとき、 　m1<m かつ　m2<m となることは有り得るのでしょうか？ 某プログラム言語を使ってデータ分析をしていたところ上記のような結果が発生しました。 直感的にはないと思うのですが。プログラムミスでしょうか？よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する