いつもお世話になっている（？）C言語標準関数、qsort。
前回の情報オリンピックでも、なんと２回も使ってしまいました。
でも、いったいどんな処理をしているのだろうか？
そう思ったことはありませんか？
（え？ない？別にいいですよ。個人の勝手です。）
そこで、どのような比較や交換をしているかを、比較関数に細工をして調べてみました。
まずはコンソールアプリケーションで実験。
► スポイラーを表示
CODE:
#include
#include
#include
int buf[26];
int num;
int comp(const void* x,const void* y) {
int a=*((int*)x);
int b=*((int*)y);
int i;
for(i=0;ib)return 1;
if(a");
scanf("%d",&num);
if(num26)return 1;
srand((unsigned int)time(NULL));
for(i=0;i<num;i++) {
buf[i]=i+'a';
}
for(i=0;i<num;i++) {
pos=rand()%(num-i);
temp=buf[pos];
buf[pos]=buf[i];
buf[i]=temp;
}
qsort(buf,num,sizeof(int),comp);
for(i=0;i<num;i++)printf("%c ",buf[i]);
puts("");
return 0;
}
※ここのシステムに不都合があるようです。'は半角の’に置き換えてください。
実行結果の一例（15を入力）
► スポイラーを表示
CODE:
o n m l j f d e c g a b h k i | o e
^ ^ |
e n m l j f d o c g a b h k i | e i
^ ^ |
e n m l j f d o c g a b h k i | o i
^ ^ |
e n m l j f d i c g a b h k o | n i
^ ^ |
e n m l j f d i c g a b h k o | k i
^ ^ |
e n m l j f d i c g a b h k o | h i
^ ^ |
e h m l j f d i c g a b n k o | m i
^ ^ |
e h m l j f d i c g a b n k o | b i
^ ^ |
e h b l j f d i c g a m n k o | l i
^ ^ |
e h b l j f d i c g a m n k o | a i
^ ^ |
e h b a j f d i c g l m n k o | j i
^ ^ |
e h b a j f d i c g l m n k o | g i
^ ^ |
e h b a g f d i c j l m n k o | f i
^ ^ |
e h b a g f d i c j l m n k o | d i
^ ^ |
e h b a g f d i c j l m n k o | c i
^ ^ |
e h b a g f d i c j l m n k o | j i
^ ^ |
e h b a g f d i c j l m n k o | c i
^ ^ |
e h b a g f d i c j l m n k o | c i
^ ^ |
e h b a g f d i c j l m n k o | l j
^ ^ |
e h b a g f d i c j l m n k o | m l
^ ^ |
e h b a g f d i c j l m n k o | n m
^ ^ |
e h b a g f d i c j l m n k o | k n
^ ^ |
e h b a g f d i c j l m n k o | o n
^ ^ |
e h b a g f d i c j l m n k o | l j
^ ^ |
e h b a g f d i c j l m n k o | m l
^ ^ |
e h b a g f d i c j l m n k o | n m
^ ^ |
e h b a g f d i c j l m n k o | k n
^ ^ |
e h b a g f d i c j l m k n o | l j
^ ^ |
e h b a g f d i c j l m k n o | m l
^ ^ |
e h b a g f d i c j l m k n o | k m
^ ^ |
e h b a g f d i c j l k m n o | l j
^ ^ |
e h b a g f d i c j l k m n o | k l
^ ^ |
e h b a g f d i c j k l m n o | k j
^ ^ |
e h b a g f d i c j k l m n o | e g
^ ^ |
e h b a g f d i c j k l m n o | e c
^ ^ |
c h b a g f d i e j k l m n o | g e
^ ^ |
c h b a e f d i g j k l m n o | h e
^ ^ |
c h b a e f d i g j k l m n o | i e
^ ^ |
c h b a e f d i g j k l m n o | d e
^ ^ |
c d b a e f h i g j k l m n o | b e
^ ^ |
c d b a e f h i g j k l m n o | a e
^ ^ |
c d b a e f h i g j k l m n o | f e
^ ^ |
c d b a e f h i g j k l m n o | f e
^ ^ |
c d b a e f h i g j k l m n o | a e
^ ^ |
c d b a e f h i g j k l m n o | h f
^ ^ |
c d b a e f h i g j k l m n o | i h
^ ^ |
c d b a e f h i g j k l m n o | g i
^ ^ |
c d b a e f h g i j k l m n o | h f
^ ^ |
c d b a e f h g i j k l m n o | g h
^ ^ |
c d b a e f g h i j k l m n o | g f
^ ^ |
c d b a e f g h i j k l m n o | d c
^ ^ |
c d b a e f g h i j k l m n o | b d
^ ^ |
c d b a e f g h i j k l m n o | a d
^ ^ |
c a b d e f g h i j k l m n o | a c
^ ^ |
c a b d e f g h i j k l m n o | b c
^ ^ |
b a c d e f g h i j k l m n o | a b
^ ^ |
a b c d e f g h i j k l m n o
|の左側が現在の配列の内容、右が何と何を比較しているかです。
比較は左にあるものが一つ目の引数、右にあるものが二つ目の引数として渡されています。
・・・少しわかりにくいですね。
そこで、DXライブラリを使ってわかりやすく表示してみました。
プログラムとソースコードは添付してあります。
これでだいぶ見やすくなりました。
赤くなっている数字が比較関数に渡された一つ目の引数、緑になっている数字が二つ目の引数です。
並べ替えの様子がアニメーションされます。
このプログラムを観察したところ、（自分の環境では）次のような動作をしていることがわかりました。
CODE:
・注目している部分の要素数が9以上の時
クイックソートを行う。
・まず、一番左、真ん中、一番右の要素を昇順に並べ替える。
・並べ替えた真ん中の要素をピポットとする。
・左から順番にピポットと比較する。
・ピポットを超える数字があったら次へ。それまで順番に比較する。
・右から順番にピポットと比較する。
・ピポット未満の数字があったら、
・左のピポットを超える数字と右のピポット未満の数字を入れ替える。
・左右それぞれ、入れ替えた次の数字からこの動作を繰り返す。
・ピポット自体とは比較しない。飛ばす。
・左からの比較場所が右からの比較場所かそれより右になったら、
・その場所で左右にわけて全体の処理をそれぞれ行う。
・注目している部分の要素数が8以下の時
・左から、そこまでの最大値とそこの値を比較する。
・一番右まで比較が済んだら、最大値と一番右の値を入れ替える。
・次に、右から二番目までこの処理を行う。
・最初の二つになるまで繰り返す。
・・・説明が下手だな。誰かもっとうまく解説してください。
まあ、百聞は一見に如かず。是非このプログラムを実際に動かして、自分の目で確かめてください。
追記
Ideoneやcodepadではどうやらマージソートのようです。
http://ideone.com/ICcZJ
http://codepad.org/EfXuv8pJ
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター