CodingFirst

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

スポンサーサイト

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

[C]選択ソートをする

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

C言語で選択ソート。

基本だけどたまには書いて筋トレ。

バブルソートの方が良い気がしてたけど、Wikipediaによれば
バブルソートと比較すると、「比較回数」は同じだが「交換回数」が少ないので、選択ソートの方が高速である。
らしい。そ、そんな気もしなくはない。。

書いた選択ソートを gist において、以下に貼りつけた。

実行例。
100個のランダム値をソートした際の比較、交換回数で、 前回のバブルソートなどの結果も合わせてみてみる。

$ for i in *.c ; do gcc $i && ./a.out ; done
         bblsort: cmp=4950.0, swp=2472.6, xor=197DFD2F
        bblsort2: cmp=4768.0, swp=2472.6, xor=197DFD2F
           qsort: cmp= 541.8, swp=??????, xor=197DFD2F
         selsort: cmp=4950.0, swp=  94.8, xor=197DFD2F

確かに交換回数がすごく少ないので、バブルソートより効率良さそうだ。
ただし、ランダムなデータであればだと思う。

アルゴリズム辞典によれば単純選択法とも呼ぶらしいんだけど、
確かに単純で分かりやすいと思う。

ソート時間のばらつきを無くし、バグのはいり込む余地のない
選択ソートを採用しました...という事例がありそう。



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

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


★☆★コメント★☆★

コメントの投稿

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

トラックバック

http://iyukki.blog56.fc2.com/tb.php/162-ed5320fe

 | HOME | 

Search

Recent Entries

Foot Print



Categories

Monthly

Recent Comments

Recent Trackbacks

Profile

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