ソートに関する質問です

質問

C言語でのプログラム作成の課題が解けなくて困っています。

バブルソートを使って、1000000個の整数データを昇順に並べ替えるプログラムを作成するというものです。
自分なりに作成したプログラムは、mallocでデータを格納する動的領域を確保して、後はシンプルにバブルソートの処理を行っています。
データ数が5，6万程度なら正常な動作が確認できるのですが、それより大量のデータ数だと、処理に時間が掛かりすぎるせいか、もしくは処理しきれずに動かなくなってしまったのか分かりませんが、プログラムの処理がいつまでたっても終わりません。
おそらくバブルソートの2重ループのあたりで、膨大な処理になってしまうのだと思うのですが、この問題についての改善策をどなたかご教授いただけませんでしょうか。

回答No.3

akayoroshi · ベストアンサー

私の使っている、それほど速くないPCでは、バブルソートで10万個の整数値をソートするのに21秒ほどかかりました。100万個だと2,100秒(35分)位でできそうです。
　コンピュータがが長い時間応答しないのが不安でしたら、外側のループ10,000回ごとにメッセージを出力してみたらどうでしょうか。20秒位ごとに反応があるでしょう。

お礼

ご返答ありがとうございます。
メッセージ出力は思いつきませんでした。
自分のPCを信じて地道に待ってみたいと思います。

回答No.5

don_go

バブル　ソートの改善・改良版というのであれば、コム　ソート
(Comb Sort)というのが有りますが、そういった類のものを
お探し(もしくは、作ろうとしている)でしょうか？

お礼

ご返答ありがとうございます。
アドバイスありがたいですけど、コムソートだと、バブルソートの性能（処理時間など）とは若干違ってくるかと思います。
バブルソートの代わりになる別モノのソートを探しているという訳ではないです。

回答No.4

Tacosan

「バブルソート」と限定してしまった時点で, 本質的な改善策は存在しません. 諦めてください.
つ～か, バブルソートなどで時間がかかりすぎるからマージソートとかクイックソートみたいな方法が考え出されてる.
もちろん (2乗オーダーであることを認めたうえでの) 本質的でない改善策は存在するかもしれませんが, 「コードを出せない」というならそれも諦めてください.

お礼

ご返答ありがとうございます。
やはりソースコードを公開しないというのはマナーが良くないですかね。(汗)

>つ～か, バブルソートなどで時間がかかりすぎるからマージソートとかクイックソートみたいな方法が考え出されてる.

おっしゃる通りです。私自身もこの時間のかかりすぎる処理を扱うという、ある意味いじわるとも取れる課題を諦めたい気持ちでいっぱいです。
ただどうしても解かなければならないものなので、諦めも肝心ですが、もうしばらく粘ってみようかと思います。

回答No.2

R_Earl

> バブルソートを使って、1000000個の整数データを昇順に並べ替えるプログラムを作成するというものです。

バブルソート限定ですか？
他のソートでは駄目なのでしょうか？

> データ数が5，6万程度なら正常な動作が確認できるのですが、それより大量のデータ数だと、処理に時間が掛かりすぎるせいか、もしくは処理しきれずに動かなくなってしまったのか分かりませんが、プログラムの処理がいつまでたっても終わりません。

バブルソートの処理時間は、大体データ数の2乗に比例します。
5万個のソートに1分かかったなら、100万個のソートには400分かかる計算になります。

お礼

ご返答ありがとうございます。
やはり膨大な時間を待つしかないのでしょうか。

>バブルソート限定ですか？
>他のソートでは駄目なのでしょうか？

限定というか、バブルソートの性能を確認するのが最終的な目的です。

回答No.1

arain

とりあえず、ソースを提示してください。
それがないと改善策もプログラムの問題もわかりませんよ。

お礼

早々とご返答していただきありがとうございます。
申し訳ないですが諸事情でソースは非公開とさせて下さい。
プログラムの誤りではなく、膨大なデータを扱う上で、シンプルなバブルソートではない何か特別な手法がないかと思い、質問させていただいた次第です。