CodingFirst

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

スポンサーサイト

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

[C]クイックソートをする

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

C言語でクイックソート。
標準でqsortがあるけど、筋トレ的に書いてみよう。

その前に、アルゴリズムを復習しよう。
クイックソート - Wikipedia
C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

一言で言うと、配列を中間値で大小に分割して再起するソートか。
実装方法に悩むけど、思いつきで書いてみた。
gist に書いたコードを以下に。

中間値は一番左の要素にして、左のバケツを決めていく方法にした。
これはこれでいいけど、奥村先生本の手法をみたら愕然。こんなコードになる頭が欲しい!

では、
コンペアとスワップを基準に前に書いたソートも含めて性能比較。

$ git clone git://gist.github.com/1476722.git sort-eg
Cloning into sort-eg...
remote: Counting objects: 26, done.
remote: Compressing objects: 100% (22/22), done.
remote: Total 26 (delta 15), reused 5 (delta 3)
Receiving objects: 100% (26/26), done.
Resolving deltas: 100% (15/15), done.
$ cd sort-eg
$ for i in *.c ; do tcc -run $i ; 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
          qsort2: cmp= 890.6, swp= 158.9, xor=197DFD2F
          qsort3: cmp= 944.1, swp= 155.1, xor=197DFD2F
         selsort: cmp=4950.0, swp=  94.8, xor=197DFD2F

安定的では無いとはいうけど、バブルソートや選択ソートに比べりゃ、やっぱり早いな。
cのqsortはかなり早そうだけど、実装がイントロソートとかなのだろう。

クイックソートは、アルゴリズムが単純で早いけど、再起を使うのが難点かな。
C言語だとスタックまで気を使う事も多いし。
もちろん、実装次第の話でもあって、例えば奥村先生本に再起を使わないコードがある。
ご利用は計画的にってとこか。

いい勉強になった。


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

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


★☆★コメント★☆★

コメントの投稿

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

トラックバック

http://iyukki.blog56.fc2.com/tb.php/169-0024d2bc

 | HOME | 

Search

Recent Entries

Foot Print



Categories

Monthly

Recent Comments

Recent Trackbacks

Profile

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