• 締切済み

多段ソート

C言語というよりはアルゴリズムの話です。 [名前], [生年月日] の2つのカラムで表される固定長の行データが羅列されたファイルがあります。 また、各カラムを比較して行をソートした場合にどの行が何番目にくるかといったインデックス情報を木構造で保持したファイルがあります。 (このファイルは行データの追加・削除時に更新される) これらのファイルを利用して、生年月日でソートし、かつ日時が同じ場合は名前順にソートした場合の上から10個分だけのデータを取り出したいのですが、効率のよい方法は無いでしょうか? 全データを読み込んでから、バブルソート等の順序を崩さないソートを多重にかけることはなるべく避けたいのです。 そのためにソート済みのインデックス的な役割を持つファイルを用意しているのですが、多段ソート時にどう応用すればよいのかわからなくなってしまいました。 例 日時、名前の順にソートされた上4つ分のデータが欲しい。 【一覧】 [1行目] 10/20, Aさん [2行目] 11/30, Fさん [3行目] 9/10, Cさん [4行目] 11/30, Bさん [5行目] 12/10, Dさん 【生年月日でソートされた インデックス】 9/10, 3行目 10/20, 1行目 11/30, 2行目 11/30, 4行目 12/10, 5行目 【名前でソートされた インデックス】 Aさん, 1行目 Bさん, 4行目 Cさん, 3行目 Dさん, 5行目 Fさん, 2行目 得たい結果 [3行目] 9/10, Cさん [1行目] 10/20, Aさん [4行目] 11/30, Bさん [2行目] 11/30, Fさん

みんなの回答

  • redfox63
  • ベストアンサー率71% (1325/1856)
回答No.3

そうでした     hash[ idate[i]-1 ] = j * 0x1000;     hash[ iname[i]-1 ] = i; の部分は += ですね両方とも それと Hash配列自体を0で初期化してやらないといけませんでした memsetなどを利用して・・・ データが膨大になったらこの方法ではちょっと無理が出てきますね ですが そうなった場合テキストベースで処理するのが困難になりそうですよ データベースを使うように変更したほうが無難なように思います

  • redfox63
  • ベストアンサー率71% (1325/1856)
回答No.2

インデックスから各行のハッシュを計算してコレを元に抽出するという具合でどうでしょう 日付が前項目と同じならハッシュ値も同じといった具合にして計算します たとえば 日付のインデックス情報が sdate[5][10], idate[5] 名前のインデックス情報が sname[5][10], iname[5] hash[5]にハッシュ値を算出 sdateに日付文字列、idateに行番号 snameに名前文字列、inameに行番号   int j = 0;   char sdummy[10];   strcpy(sdummy, sdate[0]);   for ( i=0; i < 5; i++ )   {     // 同じ日付ならハッシュカウンタはカウントしない     if ( strcmp(sdummy, sdate[i] ) )       j++;     hash[ idate[i]-1 ] = j * 0x1000;     hash[ iname[i]-1 ] = i;     strcpy( sdummy, sdata[i] );   } 同姓同名などがあるなら日付と同じようにハッシュカウンタを作って処理する必要があるでしょう # 日付などはシリアス値にに変換しておいたほうがいいかもしれませんね

unchikun
質問者

お礼

ご回答ありがとうございます. なるほど、こういう方法もあるのですね。 ご提示頂いたプログラムの hash[ iname[i]-1 ] = i; は hash[ iname[i]-1 ] += i; ということでよろしいでしょうか? 要素数が莫大な場合や3段以上のソートになった場合に,0x1000 の桁をどうするかに気をつける必要もありそうです。 また、私の勘違いでなければおそらく全インデックスデータを読み込んでからソートする必要がありますよね。 このアイデアも参考にしてみます。

  • bin-chan
  • ベストアンサー率33% (1403/4213)
回答No.1

1)【生年月日でソートされた インデックス】の希望する件数(ここでは4位まで)と生年月日と行数を取得する。 2)1)で取得した行数(x行目)の【一覧】を取得し、氏名でソート(ここでは4件のソート) ただし例外への対応が必要。 1)で希望する件数+1(ここでは5件目)も取得し、4位と同値の場合は次の値が出現するまで読む。(下手すると全件?) (【一覧】[6行目] 10/30, Gさんがあったりしたら、11/30の一人は切り捨てる必要がある)

unchikun
質問者

お礼

2)についてですが、氏名でソートすると生年月日の順序が崩れてしまう気がするのですが、同日時のものに対してのみソートを行うという解釈でよろしいでしょうか? 気持ち的には氏名でソート済みの一覧があるのにそれを多段ソートで生かせないのがなんか悔しいです。 例外の件ですが、まさにその件に似た問題で悩んでいます。 実は多段ソートに加えてフィルタ的な検索をしたいと考えています。 2値しか取りえないカラム(例えば性別 男, 女)があったとした場合、「日時、名前の順にソートされた上4つ分の男のデータが欲しい」といった探索です。 (SQLでいう SELECT * WHERE 性別='男' ORDER BY 生年月日,名前) 2つ方法があると考えていて、 1)一旦「男」をもつ行を全部抜き取ってからソーティング。抜き取る過程で「男」をもつ行データを4つ抜き取るだけではだめ(これが#1様がおっしゃっている「同値の場合は次の値が出現するまで読む」という処理に似ている) 2)ソート済みのインデックスを先頭から読んで【一覧】から「性別」を参照し、男のデータが4つを超えたら、その取得した4つのデータで残りのソーティングを行う。 男という値をもつ行データがかなり少ない場合は (1)の方法が有効だと思うのですが、男:女の比率が1:1のようなケースの場合は(2)が有効な方法になると考えており、どちらの方法にするべきかでも悩んでいます。 と話がやや脱線してしまいましたが、ご回答ありがとうございました。

関連するQ&A

  • excel 7条件一括のソート方法

    excelの表を7条件 一度の操作でソートしたいです。 A      B     C    D    E     F     G     H       data1  data2 小計1   data3  data4  小計2   合計 Aさん   28    27     55    30    25     55    110 Dさん   29    26     55    30    25     55    110 Cさん   27    28     55    29    26    55     110 Bさん   28    28     56    27    27    54     110 上記のEXCELの表があった場合の ソート条件  1 H列の数が少ない順  2 1が同じ場合Gが少ない順  3  2が同じ場合Fが少ない順 4 3が同じ場合Eが少ない順 5 4が同じ場合Dが少ない順 6 5が同じ場合Cが少ない順 7 6が同じ場合Bが少ない順 となるように するには どうしたらよいでしょうか?    間違いをなくすために 数度のソートを繰り返すことはしたくありません。         よろしくお願いいたします  

  • クライアントの自由にソートする

    お世話になっております。 現在データベースの中に下記のようなデータが存在するとします。 A B C D 1 2 3 4 (Aのカラムに1) (Bのカラムに2) と言う具合にデータが入っています。 そこで質問なのですが、クライアントの自由にABCDのカラム内のデータをソートさせるにはどのようにしたらよいでしょうか? 現在は、データベースのテーブルを下記のようにする対処方法しか思いつかないのですが、できれば上記テーブル構成のままソートさせたいのですが何か良い方法は御座いませんでしょうか? 例)  クライアントがA D B C の順にソートしたい場合 テーブル名:TB1 A  1  順位1 B  2  順位3 C  3  順位4 D  4  順位2 select * FROM TB1 A ORDER BY 順位 ASC 出力: 1 4 2 3

  • 配列のソートについて

    配列をソートした時、もともとデータのあった配列番号を記憶しておきたいのですが いい方法はないでしょうか (31,55,84,20,96,14); //1 2 3 4 5 6 ↓ (14,20,31,55,84,96) //6 4 1 2 3 5    ※ソート前の配列番号 いくつかの行(配列A)の、違う列にあるデータを抜き出して配列Bにまとめた後、配列Bをソート その後、配列Bのもともとの順番の位置の行にあるデータを上からコピーしていく感じで行ごとのソートを考えています イメージはこんな感じです a[0]=[1,512,200]; a[1]=[3,100,1]; a[2]=[4,100,265]; a[3]=[8,300,1]; //ソート対象を抜き出す b[0]=a[0][1]; b[1]=a[1][2]; b[2]=a[2][0]; b[3]=a[3][1]; b.sort(); c[0]=a[b[0]のソート前の配列番号]; c[1]=a[b[1]のソート前の配列番号]; c[2]=a[b[2]のソート前の配列番号]; c[3]=a[b[3]のソート前の配列番号];

  • こんなソートがしたいです。教えてください!

    エクセル2003で 下記のようなデータをソートし、 【ソート前】 2208550 92059184 92059174 92059174B 92059174A 92059174C 1348535 19777225 2519034 2519034D 2519034B 2519035A 2519035C 【ソート後】 1348535 19777225 2208550 2519034 2519034B 2519034D 2519035A 2519035C 92059184 92059174 92059174A 92059174B 92059174C 上記ソート後の結果を得られるマクロを作りたいです。 よろしくお願いいたします。

  • csvファイルの読込みとソート

    いつも大変参考にさせていただいております。 csvファイルの読み込みとソートをしたく、ネットや過去ログ等を相当調べたのですが、完全に詰まってしまいました。 (検索キーワード:「php csv ソート」「php 二次元配列 ソート」など) とても困っています。どなたかよろしくお願いします。 以下のようなcsvファイルを読み込みソートしたいのです。 ■csvファイル 20110803, A, りんご 20111215, B, みかん 20110306, A, みかん 20110620, A, りんご 20110215, B, りんご ■個別にやりたい処理 (1)、左列の日付で昇順ソートしてすべて表示 (2)、「A」を含む行をすべて表示(日付順) (3)、「A」+「りんご」を含む行をすべて表示(日付順) □補足 csvをfgetcsvで読み込み、テーブルに入れて表示するところまではできました。 csvの行は増えていきます(max100行位)。列は固定。

    • ベストアンサー
    • PHP
  • エクセル2002でのソートについて

    A B C 1 A1 B1 C1 2 __ B2 C2 3 A5 B5 C5 4 __ B4 C4 5 A3 B3 C3 6 __ B6 C6    ↓ソート A B C 1 A1 B1 C1 2 __ B2 C2 3 A3 B3 C3 4 __ B4 C4 5 A5 B5 C5 6 __ B6 C6 (1)A列をキーに (2)1と2行,3と4行,5と6行を一纏めに ソートする方法はありますでしょうか?

  • 配列のソートについて質問です。

    配列のソートについて質問です。 2つのキーで配列の中身をソートしたいのですが、スマートな書き方があれば教えてください。 そもそも間違っている、などのご指摘でもありがたいです。 @t1 = map {(split /,/)[1]} @data; @t2 = map {(split /,/)[2]} @data; @data = @data[sort {$t1[$a] <=> $t1[$b] or $t2[$a] <=> $t2[$b]} 0 .. $#t1]; @dataの内容 A,1,2 B,1,3 C,2,1 D,3,2 E,3,1 F,1,1 出力結果 F,1,1 A,1,2 B,1,3 C,2,1 E,3,1 D,3,2 よろしくお願いします。

    • ベストアンサー
    • Perl
  • excel ソート(容量大?)すると 2分割でソートされるけど解決方法は

    500行25列くらいのデータを、ある列の種別順でソートすると全部の行が一度にソート出来ずに、途中まで行くとそこから再度ソートされます (例)名前あいうえお順でソート 1 青山 2 木村 ー 200 和田 201 青木 202 川村 ー 500 和久 本当は1~500行まで通じてソートしたいのですが、なぜか途中でソートが分割されてしましいます。何か一度にソート出来る容量等の制限が有るのでしょうか。初心者なので出来るだけ簡単に教えてください 宜しくお願いします。

  • エクセル表で異なった分類でソートする方法

     A列に分類番号のA・B・Cを打ち、横にデータを記入していく。横列のC又はD(縦列)にア・イ・ウの頭文字をつけてデータ(人名や語句)を打っていく。このようにして作った表を、(1)ABCをソートして並べ替える(Aグループ、Bグループの順に並ぶ。次に(2)Aグループのなかを、アイウ順に並べ替えたい。そのような操作が出来る方法を教えてください。  私が試みたら、C列だけがソートされて、横のデータが付いていかないのです。空欄があるせいでしょうか。それとも?ソートは、C欄全体を選択し、「降順」をクリックしています、表全体(AからE,Fまで選択したら、どの指標で(AかCか)分からないと思って。  試行錯誤で使っています。どうぞ知恵を貸してください。

  • Excel上でのデータソートの方法をご教授下さい

    Microsoft Excelでの、ソートについてご教授下さい。  例えば、蔵書リストを作成した場合、A列に著者名、B列に書名、C列に価格と入力していくとします。 このとき、C列を対象としてソートすると、そのC列は昇順なり降順なりで価格順としてソートされますが、A列B列のデータとC列のデータが食い違ってしまいます。  これを、エクスプローラのファイル一覧のように、A列の著者名でソートすると、それをB列C列にも反映させ、蔵書リストを著者順にも書名順にも価格順にも一行一冊づつ並べ替えるにはどうしたらよいのでしょうか。   なんとかうまく説明したいのですが、稚拙極まる質問の表現で大変恥ずかしく思います。 どなたか質問の内容をお酌み取り頂き、教えて頂いたら幸甚に存じます。  また、既出質問、あるいは各種マニュアルを精査すればこの方法が記載されてる事と思います。 それらを横着し、皆様の知識と善意に安直に頼る姿勢をお許し願いたいと存じます。