C言語でのソートについての質問

Question

C言語で順序の安定性があるソートをしたいのですが、標準ライブラリにはqsortメソッドしか見つかりませんでした。
クイックソートは安定でないはずなので、こういう場合自分でバブルや選択ソートなどを実装するのが普通ですか？
今回はソートの速さは一切考慮しません。

Answer 1

実は、qsortって、仕様上はアルゴリズムを規定していないので、必ずしもクイックソートで実装されているとは限らないのですよ。いわゆる処理系依存というやつです。とはいえ、ほぼクイックソートでしょうけど。

それはともかく、おっしゃる通り標準機能でできない場合は自分でなんとかするしかありませんね。あるいは誰かが作ったものが使えるならそれでもいいですし（ライブラリというやつです）。

速さを考慮しなくて良いのであれば、一番簡単に実装できるものでいいと思います。
ただし、「普通は」処理時間も考慮に入れないといけないことが多いので、アルゴリズムの選定は重要になります。

Comments

[Chikin]

みなさん回答ありがとうございました。
やはり自分で実装することが多いんですね。
バブルや選択は簡単そうですが、ヒープやマージなどはバグが出そうで心配になりますね。

[catsforepaw]

> バグが出そうで心配になりますね。
そうなんです。ですので、まずは要求を満たす一番簡単な方法で作って、満足できないときは別の方法を試すということをよくやります。

Answer 2

私なら構造体で2進木を作成しますね。
データ数を気にすることなく、順序安定性も保たれスピードもいいですから。

Answer 3

かなり前ですが、同じく qsort では順序安定性がたもてないため、自分でソートを実装しました。
そのときは、バブルソートで実用になりました。

思い起こしてみると、オンメモリ上で完結するソートする需要なんてあまり無く、たいていはファイルがらみだったので、自前で実装する事が多かったです。はい。