構造体のリストをソートしたい。

質問

ある名簿のリストを作りました。
以下のような構造体で、

typedef struct meibo{

char name[10];
int old;
struct meibo *next;

}MEIBO;

これを、ポインタp->next->nameをたどっていって、名前が辞書順になるようにリストを作ったのですが、
これを年齢順にソートして表示させたいんです。
どんな方法があるんでしょうか？
一旦すべてを配列に格納して、クイックソート…とかも考えたのですが、すごく領域をとるし、なんか２度手間（最初から配列に順に格納していけばよかったなぁ・・・と。
それでもやっぱり最初から名列順にするときから配列に入れておくほうがいいのでしょうか？
教えてください。

（最初から年齢を比較してリストを作れば・・ってのはなしで、名列順のリストが存在するものとしてください。）

回答No.4

terra5 · ベストアンサー

ソートの方法は既に回答があるので、配列とリストについて。

データ構造として配列を選ぶか,リストを選ぶかは使い方とか目的等によります。
リストを選んだ方がいいケースは、例えばデータの追加、削除が頻繁に発生しデータ数が多い場合です。
具体的に言えば10万のデータがあって、先頭でデータの追加,削除が発生し、データが配列の場合は、99999のデータの移動が生じます。
リストの場合はリンクのつけかえだけですので、
データの移動は発生しません。
この質問の場合は現状ではどちらがいいかはわかりません。

ところで、この場合はクイックソートは向かない気がします。
というのはクイックソートでは比較の結果が同じ場合,
順番が保存されないからです。

例えば,
...
佐藤、10才
鈴木、10才
田中、10才
...
というデータがあった場合、年齢でソートして名前の順番が変わることがあります。

回答No.5

επιστημη（@episteme）

linked-listをそこそこのスピードでソートしたいなら、マージ・ソートがいいんじゃないかしら。

回答No.3

shige_70

なにもひとつの構造体でひとつのリスト構造しか作れないわけではないのですから、メンバにもうひとつポインタを追加して、年齢順リストを作ってあげる、という方法は如何でしょうか。

回答No.2

winterofmeei

MEIBOのポインタ配列をつくり、そこに各要素のポインタを格納して、年齢順に並べ替える方法はどうでしょうか？元々のリスト構造を壊すことなく、年齢順に要素を取得することができるようになります。

MEIBO *tmpList["要素数"]; // 要素数が可変なら動的に割り当てる

// tmpListに各要素のポインタを格納

// qsortでも何でも使ってソートする

// tmpListを参考に出力する

回答No.1

Tsukasa0215

malloc関数でメモリを一時作業領域としてソートする方法もあります。

また何もメモリ上【だけ】で作業をする必要は無いですよ。方法としてはファイルに書き出すとか。