個別のアルゴリズムをつつく3－マージソート。一旦分割♪これマジだよぉ。

このアルゴリズムは 合併法 の考え方をもとに作られたアルゴリズムなんだ。 考え方をリンク先でつついてからこのアルゴリズムをつついてね♪
合併法はつついた？じゃあ、マージソートを一緒につつこう！ マージソートの手順は次の通りだピヨォ。


【マージソートの大まかな流れ】

1. 扱える大きさまでデータを二分割していく。データをつついて割っていくんだ。
2. 細かに分かれたデータをソートしながら合体させていく。小さいから簡単♪
3. 全てのデータ片を合体したらあら不思議。データが整列しているよ♪

てな寸法さ。
ドリィちゃん「相変わらず大雑把ね。」
でも、マージソートってイメージはこんなもんじゃない？
ドリィちゃん「まぁね。どうせこの説明は実装のおまけだからね。」
そっそれは酷い・・・でも言い返せない。まぁ、とにかく言語との実装を見て見て♪
ドリィちゃん「ちょっと、拗ねたの。もぉ・・・。仕方がないわね。私が説明しておくわ。
このソートはバブルソートよりも効率がいいと言われているわ。何故かというと、比較回数が少なくなるから。2分割にして比較するところがポイントなんだけど、 比較する場合は両方の先頭だけ比較するだけだし、途中で片一方がなくなったとき、後は残った方を出力するだけになるからね。その辺に注意してコードを見ればいいわ。後、このソートは再帰が伴うわ。覚悟してね。」


【言語ごとの実装例】

• C++・・・ 型固定

アルゴリズムの方法論をつつく5－合併法。小さな事からコツコツと

今回は合併法という考え方をつつくピヨ。合併法というのは分割統治法という考えの元で作られたソートアルゴリズムの分類なんだ。 分割統治法については後でソフトウェア工学の記事で詳しく説明するピヨ。 だから今回は簡潔に囀るね。
分割統治法とは問題を解決できない時は、細分化して考えれば解けるという考え方ピヨ。例えば、1兆件のデータをソートする状況を想像してみて。1兆件ものデータをどうやってソートするのだろう。何故この件数が問題なのかというと、 メモリに格納できないから普通のソートアルゴリズムは使えないからなんだ。そこで活躍するのが合併法のソートアルゴリズムなんだ。 合併法ではこのような時は、「 小さく小分けしてソートし、後でそれをまとめればいいじゃん。 」と考えて実装するピヨッ！部屋が散らかった時、部屋を4つの区画と考えて、１区画1日掃除するのと同じピヨね。
という事で、これから個別のアルゴリズムについてつついていくピヨォ～！楽しみにしてね♪

個別のアルゴリズムをつつく2－挿入ソート。ちょっと右へ寄ってくださる？

基本的な考え方は アルゴリズムの方法論をつつく4－挿入法。あるべき位置へおけば整列完了！ 見てね♪
リンク先で紹介したトランプのイメージでアルゴリズムを捉えるいいよ。もし、それでもピンとこない人は、紙を細かく切ってそこに０～９の数字を書いて、実際にソートしてみるか、満員電車か映画の座席に座るとき「ちょっと右へよって」とおばちゃんやおっちゃんが言っている光景を想像しよう。
でも一番理解が早いのは実装を見る事ピヨ♪これからここへリンクを張っていくよ。楽しみにしてね。


【言語別挿入ソートの実装例】

• C++・・・ 値固定型

アルゴリズムの方法論をつつく4－挿入法。あるべき位置へおけば整列完了！

今回はまたソートへ戻って挿入法という考え方をつつくピヨ♪ 挿入法の考え方は・・・

データが増える毎に正しい位置へ格納すれば整列している状態を保てる。

という考え方なんだ。言葉では分かりにくいからトランプを思い浮かべてみよう。 トランプをシャッフルして、１枚づつ引いたカードを横へ並べる方法を考えてみるピヨ。ここでは、左から右へ数字が大きくなっているとルールを決めるとしよう。この場合、まず４を引いたとしても他のトランプはないから４をそのまま置くピヨ。

4

次に１を引いたとすると、１は４の前に置かなくちゃならないから・・・ まず４を右へ置いて１の場所を空ける

○  4

そして１のカードを置く

1  4

そしてまた引くと今度は６だった。6の場合は４と比べて大きいから４の右へ置く

1  4  6

えいやぁー。今度は５のカードが出たピヨ。この場合は６の方が大きいから６を右へ置く

1  4   ○  6

そして空白の部分に５のカードを置くピヨッ♪

1  4  5  6

こんな具合にして挿入する位置を探して行くのが挿入法だピヨ。 説明しにくいから基本挿入法を例につついたけど、考え方は変わらないピヨ。それじゃあ、これから個別のアルゴリズムをつついていくピヨ。楽しみにしてね。

アルゴリズムの方法論をつつく3－番兵法。見張り番で効率UP。

前回の線形探索法 はひとつづつ調べるという単純明快なアルゴリズムピヨ。だけど、単純ゆえに効率も悪かったんだ。 具体的に言うと、最後まで到達したか毎回判定 するのが非効率的ピヨ。この末尾判定処理は 初めから求める値があればなくせる 余分な処理ピヨッチ♪ でも無いから困っているんだから、何らかの工夫が必要となるんだ。 その工夫は答えを聞けば単純明快、探している値を最後に用意すればいいんだ。ちょっとズルイ気もするけど、そうすればカウント変数はいらないピヨ。 その代り最大データ数＋１の領域が必要となるピヨ。 でも、１つぐらい領域をとっても毎回判定するよりましだよね。
いつものように下にプログラム言語ごとの実装例へのリンクを張っていくピヨ。 ちびちび作っていくから、楽しみしてね♪


【番兵法（番犬法）の実装例】

• C++・・・値固定型。

アルゴリズムの方法論をつつく2－線形探索。仕方がない、逐一調べよう。

新人教師田中は、今日も頭を抱えていました。それにみかねた山田は呆れつつ声をかけました。
山田「どうしたのぉん」
田中「それが、光原君のデータを探しているんですが、ディクスが書類の山で、どうやって見つけたらいいのかわかりません。」
山田「はぁ、何をしているの？まったく・・・ほんと愚図よねぇ。そんなんで教師出来るのん？」
田中「そんな事言わずにまたマジック見せて下さいよぉー」
山田「アルゴリズムをマジックという時点で見込ないわん。でも、まぁ、あちきに付き合ってくれるのなら教えてあげてもいいわよん。」
田中（恐ろしい・・・でも背に腹は代えられない！）「分かりました。僕に出来る範囲で付き合いましょう。」
山田「じゃあねぇ、こんなカオスな場合は線形探索法をやるわん。」
田中「それはどんなマジックですか？」
山田「それわねぇん。逐一探すのよん。」
田中「えっ！それだけ？」
山田「お馬鹿！整列していないデータを探す場合、逐次探索しかないでしょう！あんたが初めから机の上を整理整頓していればこんなことにはならなかったのよん。」
田中「ごもっともです。わかりました。一枚一枚書類を探しましょう。」


ストーリーを読めば何となくわかると思うけど、線形探索(別名：逐次探索)とは、その名の通り逐一データを探すアルゴリズムピヨォッ！初めからデータを整理整頓しておかないのが悪いピヨね。 このアルゴリズムは勿論、あまり効率は良くないピヨ。 だから探索アルゴリズムはソートアルゴリズムとの併用が望ましいピヨ。
線形探索法は基本的に単純なアルゴリズムなので、実装については下にリンクを張っていくピヨ。


【線形探索法】

• C++・・・値固定型

個別のアルゴリズムをつつく1－バブルソート。バブルバスガール♪

今回はソートアルゴリズムの基礎バブルソートをつつくピヨ。バブルソートの考え方は

隣と比べて、隣の方が小さければ交換する。これを全ての要素に対して行えば整列している状態になる。

というものピヨ。この考えは文字では分かりにくいから例を挙げてつつくピヨ。



【例：0～9がある場合】
簡単な例としてこんなデータを整列する事を想像しよう。

ごちゃごちゃだ・・・
9  3  5  6  2  8  7  0  1  4

バブルソートでは、まずは最初の数値9と３を比べる。そして、３の方が小さいから交換するピヨ。チェーンジ！

まだまだごちゃごちゃだ・・・
3  9  5  6  2  8  7  0  1  4

次は２番目の数値９と５を比べるピヨォ。もちろん５の方が小さいからまたチェーンジ！

9「俺また移動かよ・・・」
3  5  9  6  2  8  7  0  1  4

このようにして最後まですると・・・

9「俺最後まで移動された。これって左遷ってやつかなorz」
3  5  6  2  8  7  0  1  4  9

最後まで来たらまた最初から比較交換するピヨ。

3「俺の方が小さいから交換はできないぜ」
3  5  6  2  8  7  0  1  4  9

このように比較して小さかったら何もしないピヨ。うーんもどかしいぃぃ。
後は同じようにして最後まで行くと・・・
9「おい、インドリ。俺はどうせ最後なんだから放っておいてくれ！」
ごめん、ごめん。このように比較するべき回数は減っていくから最後から決まるアルゴリズムと言えるピヨ。 この辺が初心者には難しいと思うピヨ。言語ごとの実装を用意するから デバッガで１行ごとに実行していく とわかりやすいピヨ。出来上がったらこの下にリンクを追加するピヨ。ちょっと待っててね。


【実装リスト】

• なでしこ・・・ 型固定

アルゴリズムの方法論をつつく1－交換法。交換しあったら並んだよ。

前回は選択法という考え方をつついたから、今度は交換法という考え方をつつくピヨ。選択法の場合は、ふさわしい要素を選択するという考え方だったけど、交換法の場合は

要素の交換を繰り返せば結果として整列している

という考え方なんだ。この方法は選択法よりも抽象的なので、実際のアルゴリズムをつつかないとわかりにくいと思うピヨ。だから今回は下手な説明を止めて、交換法に属する実際のアルゴリズムをつつく事にするピヨ。

アルゴリズムをつつく4－プログラム言語とアルゴリズムの実装。

次に、データ量の場合について囀るピヨ。対象となるデータの量が多い場合格納場所を考える必要があるピヨ。何故かというと、膨大なデータ量をそのまま配列とかに格納するとメモリがパンクする。こんな場合は ファイルかデータベース を使用するしかない。こうなると、作業用の場所を考える必要があり、大変困難になるピヨ。という事は当然メモリに負担をかけないような実装が要求されるピヨ。これらの2点に注意して実装する必要があるピヨォー。みんな注意してね

個別のアルゴリズムをつつく0－基本選択ソート。主は此処になおれ！

「アルゴリズムの方法論をつつく0－選択法。何を選択するの？」の記事で選択法という考え方をつついたから、今度は具体的なアルゴリズムをつっつくピヨ♪何にしようかな・・・決めた！基本選択ソートをつつくピヨッ！ 基本選択ソートは最小値を格納する場所を特定しながら選択するやり方 と考えるとわかりやすいピヨ。抽象的な説明では分かりにくいと思うから具体例を挙げるピヨォツ！

【例：0～9がある場合】
簡単な例としてこんなデータを整列する事を想像しよう。

ごちゃごちゃだ・・・
9  3  5  6  2  8  7  0  1  4

基本選択法ではまず位置を決める。もちろん0からピヨ。
0番目に入れる数値は＝X
次に1番目～9番目までの数値内で一番小さい数値を探す。
一番小さい数値はもちろん0だよね。だから・・・
0番目に入れる数値は＝0
でもちょっとまって！今現在9が居るピヨ。だから場所を変わってもらおう。
その結果データは次のようになるピヨ。

ちょっとは整理できたかな？
0  3  5  6  2  8  7  9  1  4 

緑色が確定した数値で、黄色は位置が変更された直後の数値だッピヨ♪
次に同じ事をすると・・・その結果は

少しましになったかな？？
0  1  5  6  2  8  7  9  3  4 

これを最後まで繰り返すと・・・

0 1 2 3 4 5 6 7 8 9
となるピヨピヨね♪
具体的なプログラムは下の部分にリンクを張っていくピヨ。楽しみにしてね♪


【実装例】

• C#・・・型固定、 型固定再帰型。
• Java・・・型固定