CodingFirst

C言語、Perl、JavaScript、最近はPythonも。出来上がったものより、プログラムを書くことが好き。あと、スイーツ。

スポンサーサイト

  • このエントリーをはてなブックマークに追加
  • web拍手 by FC2
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[C]バブルソートをする

  • このエントリーをはてなブックマークに追加
  • web拍手 by FC2

C言語でバブルソート。
超基本だけど、たまには書いてみないと。筋トレのようなものかな。

バブルソートを書いて gistにあげた。
ランダムな100個の数値をバブルソートし、比較回数を出力した。

以下にgistと実行結果

$ gcc bblsort-eg.c && ./a.out
calls: 4950.000, xor: 197DFD2F

qsortを使った例。

$ gcc qsort-eg.c && ./a.out
calls: 541.826, xor: 197DFD2F

プログラム自体は難しくないので結果に注目してみる。
バブルソートが 4950 回、
クイックソートが 541 回とでた。
クイックソートの平均は n log n = 460 なので誤差があるけど、10倍の開き。

ちょっと改良した bblsort_eg2.c を作ってみたけど大差なし。

$ gcc bblsort-eg2.c && ./a.out
calls: 4767.998, xor: 197DFD2F

と、散々な結果がでてしまうけれど、
バブルソートを否定してるわけではない。

バブルソートは、
プログラムが単純、
ソートにメモリが不要、
ある程度ソートされてれば遅くもない。

大抵、ソートするデータって規則性あるし、
ソートを途中で中断しやすいのが地味に便利だったりもする。
なので、バブルソートはよくお世話になる。


C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)
(1991/03)
奥村 晴彦

商品詳細を見る
スポンサーサイト


★☆★コメント★☆★

コメントの投稿

Name
Subject
Mail
URI
Comment
Pass
Secret 管理者にだけ表示を許可する

トラックバック

http://iyukki.blog56.fc2.com/tb.php/161-9cca9a29

 | HOME | 

Search

Recent Entries

Foot Print



Categories

Monthly

Recent Comments

Recent Trackbacks

Profile

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。