多段ソート

質問

C言語というよりはアルゴリズムの話です。

[名前], [生年月日]
の２つのカラムで表される固定長の行データが羅列されたファイルがあります。
また、各カラムを比較して行をソートした場合にどの行が何番目にくるかといったインデックス情報を木構造で保持したファイルがあります。
（このファイルは行データの追加・削除時に更新される）

これらのファイルを利用して、生年月日でソートし、かつ日時が同じ場合は名前順にソートした場合の上から１０個分だけのデータを取り出したいのですが、効率のよい方法は無いでしょうか？

全データを読み込んでから、バブルソート等の順序を崩さないソートを多重にかけることはなるべく避けたいのです。
そのためにソート済みのインデックス的な役割を持つファイルを用意しているのですが、多段ソート時にどう応用すればよいのかわからなくなってしまいました。

例

日時、名前の順にソートされた上４つ分のデータが欲しい。

【一覧】

[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さん

回答No.3

redfox63

そうでした
　　　　hash[ idate[i]-1 ] = j * 0x1000;
　　　　hash[ iname[i]-1 ] = i;
の部分は += ですね両方とも
それと Hash配列自体を0で初期化してやらないといけませんでした
memsetなどを利用して・・・

データが膨大になったらこの方法ではちょっと無理が出てきますね
ですが そうなった場合テキストベースで処理するのが困難になりそうですよ
データベースを使うように変更したほうが無難なように思います

回答No.2

redfox63

インデックスから各行のハッシュを計算してコレを元に抽出するという具合でどうでしょう

日付が前項目と同じならハッシュ値も同じといった具合にして計算します

たとえば
日付のインデックス情報が 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] );
　　}

同姓同名などがあるなら日付と同じようにハッシュカウンタを作って処理する必要があるでしょう
# 日付などはシリアス値にに変換しておいたほうがいいかもしれませんね

お礼

ご回答ありがとうございます．
なるほど、こういう方法もあるのですね。

ご提示頂いたプログラムの
hash[ iname[i]-1 ] = i;
は
hash[ iname[i]-1 ] += i;
ということでよろしいでしょうか？

要素数が莫大な場合や３段以上のソートになった場合に，0x1000 の桁をどうするかに気をつける必要もありそうです。
また、私の勘違いでなければおそらく全インデックスデータを読み込んでからソートする必要がありますよね。

このアイデアも参考にしてみます。

回答No.1

bin-chan

１）【生年月日でソートされた インデックス】の希望する件数（ここでは４位まで）と生年月日と行数を取得する。
２）１）で取得した行数（x行目）の【一覧】を取得し、氏名でソート（ここでは４件のソート）

ただし例外への対応が必要。
１）で希望する件数＋１（ここでは５件目）も取得し、４位と同値の場合は次の値が出現するまで読む。（下手すると全件？）
（【一覧】[6行目] 10/30, Gさんがあったりしたら、11/30の一人は切り捨てる必要がある）

お礼

2)についてですが、氏名でソートすると生年月日の順序が崩れてしまう気がするのですが、同日時のものに対してのみソートを行うという解釈でよろしいでしょうか？

気持ち的には氏名でソート済みの一覧があるのにそれを多段ソートで生かせないのがなんか悔しいです。

例外の件ですが、まさにその件に似た問題で悩んでいます。
実は多段ソートに加えてフィルタ的な検索をしたいと考えています。
２値しか取りえないカラム(例えば性別 男, 女)があったとした場合、「日時、名前の順にソートされた上４つ分の男のデータが欲しい」といった探索です。
（SQLでいう SELECT * WHERE 性別='男' ORDER BY 生年月日,名前)

２つ方法があると考えていて、

１）一旦「男」をもつ行を全部抜き取ってからソーティング。抜き取る過程で「男」をもつ行データを４つ抜き取るだけではだめ（これが#1様がおっしゃっている「同値の場合は次の値が出現するまで読む」という処理に似ている）

２）ソート済みのインデックスを先頭から読んで【一覧】から「性別」を参照し、男のデータが４つを超えたら、その取得した４つのデータで残りのソーティングを行う。

男という値をもつ行データがかなり少ない場合は （１）の方法が有効だと思うのですが、男:女の比率が1:1のようなケースの場合は（２）が有効な方法になると考えており、どちらの方法にするべきかでも悩んでいます。

と話がやや脱線してしまいましたが、ご回答ありがとうございました。