アルゴリズムの勉強と言えば、まず最初に出てくるのが「ソーティングアルゴリズム」でしょう。
葬儀では『可哀想なジョージ。心臓病になるまではソートルーチンもちゃんと動いていたのに』
と言ってるのが本物のプログラマだ
という言葉もありますしね〜。
# from "Real Programmers Don't Use PASCAL"
とりあえず、今回は基本となる (らしい) 3 種類です。
浜工情報処理部で最初に習ったソート法です。 データの先頭から末尾に向かって、各要素に次のような処理を行います。
簡単に言えば、「データの中から一番大きい / 小さいモノを次々に取っていく」 ということです。次々に選択して取っていくから、選択法。
ただ、我が浜工情報処理部では別の方法で習ったため、バブルソートとの区別が付きにくくなってしまいました。 処理部で教えてたコードはサンプルコードの中にあります。こっちの方がソースは短くなるんですが、交換回数は増えます。
日本語では「(隣接) 交換法」と言います。なんか訳分かんない名前ですが、方法は簡単です。 浜工情報処理部では 2 番目に習いました。その次がクイックソート。 同様に、データの先頭から末尾に向かって処理を行います。
やっぱり文章だと解りづらいですね。基本的には「すぐ右と比較して交換」です。 これを繰り返すと、右端に最も大きい or 小さいデータが来ますから、次は残りのデータで同じ事をやって…… ってのを繰り替えしていけば、最終的には全てのデータが順番通りに並ぶことになります。 選択法とは違い、右端からだんだんソートされていきます。
「ソート済みの部分に、次々に値がくっついていって大きくなる」様子が、 水の泡が大きくなっていくのに似ているので「バブルソート」と言うのですが、 最初に聞いたときは「何じゃそりゃ？」と思いました。(苦笑
英語のまま「insertion sort」と言うこともあります。 でも、選択法を「selection sort」とはあまり呼びません。何故だ。手順は以下の通り。
既にソート済みの部分に、新しい要素を次々に挿入していくので、 挿入ソートといいます。挿入の様子はバブルソートに似ています。
このソートの特徴として、「部分的にソートされているデータに関して高速」というのがあります。 そのため、大まかなソートを他の方法でやってしまって、仕上げに挿入ソートを掛ける、ということが行われる……らしいです。
ソートの勉強で出てくる自作関数のプロトタイプって、たいてい
void hogesort( int array[], int num );みたいな汎用性のかけらもないモノだったりするわけですけど、こんなモノを組んだって後々役に立つワケが無い。 というわけで、今回の関数のプロトタイプは
void bubblesort( void *base, size_t nel, size_t width, int( *compar )( const void *x, const void *y ) );のような、qsort() と同じ引数を持つモノにしてみました。 これなら、後々何かに利用することがあっても問題なく使えます。
Cで書いてみたサンプル (download)
今回はCで書いてみました。ポインタでごりごり弄ってるので、一寸判り辛いかも知れません。
関数 swap() 中で作業領域用に動的メモリ確保をしていて、これが動作速度の 足枷になっていること間違いなし って感じなんですが、 やっぱり呼び出し側 (ソート本体か main() )で、作業領域を用意してやるのが良いんですかねぇ……。
shi3z大先生が実装を試していたらしい「最初にたっぷり動的確保して、あとはそれを自前で切り分けて配給」 っていうコードも組んでみたいですな。C++ で new をオーバーロードしてやれば出来るかな ?
こういうプログラムを組んでいていつも気になるのがエラー処理。
fprintf( stderr, "Memory arrocation error.\n" );
って感じのモノを、本なんかでよく見かけるのですが、
MS-DOS の場合の stdout と stderr の違いって何なんでしょう。(爆
ちなみに、今回は puts() でエラーメッセージ吐かせてます。ひぃ(汗
本当なら、C なら setjmp() 〜 longjmp()、C++ なら try 〜 catch 文で エラー処理をするとかが望ましいんでしょうけど、今回は特にそういうことはやっていません。