双方向リストのソート方法について。

質問

単刀直入に言いまして、双方向リストのデータを入れ替えるのではなくて、リスト前後を指すポインタの繋ぎ代えをして、ある一定条件に従ったリストへのソートをしたいと思っています。

リスト構造の前後にダミーを置いて……という方法は取りたくなく、出来るだけメモリを節約した方法が知りたいです。

また、そのリスト数は大体２０個くらいで、１秒間に大体５０～６０回くらい呼ばれるモノです。
リストのデータ数は比較的大きい物です。

参考になる書籍とかでも構いませんので、是非とも教えて下さい。

回答No.2

tomorot

ポインタ操作で入れ換えするためのリスト構造だと思いますが(＾＾；

番兵を使わずに、なら、先頭と末尾と現在地を指すポインタを用意して、
繋がっていないところをNULLにしておいて、
先頭からバブルソートしていくのがいいかと思います。

要素数が20個程度なら、バブルソートでも速度的な問題はさほどありません。
クイックソートするには、ランダムアクセスできないリストは不利ですしね。

一応、バブルソートのアルゴリズムを簡単に。
まず、現在地を先頭にする。
現在地と次の要素と比較。
（昇順に並べ替えると仮定して）
次の要素の方が大きければ入れ換え。小さければそのまま。
現在地を次の要素にして、また、次の要素と比較、入れ換え。
現在地の次の要素が末尾ならば、末尾を現在地（末尾のひとつ手前）にして、
先頭に戻る。

入れ換えは、
０->１->２->３、現在地＝１として、１と２を入れ換えるならば、

1：現在地(１)の前の要素(０)の次を、現在地の次の要素(２)にする。
2：現在地(１)の次の要素(２)の前を、現在地の前の要素(０)にする。
3：現在地(１)の前を、現在地の次の要素(２)にする。
4：現在地(１)の次の要素(２)の次の要素(３)の前を、現在地(１)にする。
5：現在地(１)の次を、現在地の前の要素(２)の次の要素(３)にする。
6：現在地(１)の前の要素(２)の次を、現在地(１)にする。
7：最後に、入れ換えしなかった場合と同じにするために、現在地を現在地の前の要素にする。

以上で入れ換えできるはず。
机上でしか試してないので、間違っていたらごめんなさい。

具体的なコードは、敢えて書きません。
参考図書は、やっぱり「Cで学ぶデータ構造とアルゴリズム」かな。。。

参考URL：

http://www.amazon.co.jp/exec/obidos/ASIN/4274078272/qid=1119463275/sr=8-5/ref=sr_8_xs_ap_i5_xgl14/250-4827413-8033851

回答No.1

xcrOSgS2wY

「メモリが節約できさえすれば速度は問わない」という条件ならば古典的なバブルソートが使えますが・・・
そうではなくて、メモリは節約したいが速度はO(n log n)にしたいという条件でしょうか。