Version 13.21
ソートのまとめ

「というわけで、ソート編は今回で終わりです」
『早！　ってゆーかバブルソートとクイックソート、マージソートの３つし
か教わらなかったけど』
「実際には、ソートのアルゴリズムはまだまだたくさんあります。ただ、使
う上ではこの３つ知っていれば十分」
『ってゆーかマージソートひとつで十分そう』
「さて、こうしてアルゴリズムを説明してきたわけだけど、そこから学び
取って欲しいことは、次の４つ」

・しくみ
・使い方
・コードへの置き換え
・アルゴリズムの考え方

「まず〈しくみ〉と〈使い方〉から。このふたつはセットで、ソートのアル
ゴリズムを〈使う側〉としての見方です」
『ん、仕組みは、それ知ってないと安定ソートかそうじゃないかわかんない
し、使い方は、そのまんま使い方がわかんなきゃ意味ない、ってとこ？』
「そんなところ。ソートはプログラムでよく使う機能だから、まずは使えな
いとしょうがないからね」
『次の〈コードへの置き換え〉って、よーするにアルゴリズムの考え方を、
プログラムにどう置き換えるかってことね』
「そう」
『じゃあ教えてもらってない』
「う”」
『コード見せてもらっても、どう置き換えるのかわかんなかった』
「実際、これは説明難しいかも。一番難しいのは……たとえば、マージソー
トで」

(3,4,9)
(5,8)
　↓
[,,,,]

「このマージの場合」
『？　これ、難しい？』
「頭の中でやる場合にはね。プログラムに置き換える場合、これを【法則】
に変換しなきゃいけないから」
『法則？』
「つまり」

1.ふたつの配列の一番左の数を比較する。
2.上が小さければ上の値を、下が小さければ下の値をマージ先に追加する。
3.追加した数を消す。
4.すべての数を比較し終えたら終了。そうでなければ 1 へ戻る。

「という感じの法則」
『そっか、プログラムに置き換える時には、こういうふうに法則を作らな
きゃいけないんだ』
「しかも、これは不完全なんです」
『え”』
「まず 2 の〈マージ先に追加〉」
『あ、これって CStringArray とかそーゆーのじゃないと……』
「そういうこと。同じく〈追加した数を消す〉もね」
『前回のプログラムだと……インデックスナンバーずらしたりしなきゃいけ
ないんだね』
「それを含めて、プログラムに近い形で書くと」

1.インデックスナンバー IndexA と IndexB を作成して 0 をセットする。
2.上の配列の IndexA の値を取得する。
3.下の配列の IndexB の値を取得する。
4. 2 と 3 を比較する。
5. 4 の結果の小さい方を、マージ先の IndexA + IndexB に書き込む。
6. 4 の結果で、小さい方が上の配列なら IndexA + 1 する。
7. 4 の結果で、小さい方が下の配列なら IndexB + 1 する。
8. IndexA と IndexB 両方とも配列のサイズを超えていたら終了。
9. それ以外は 2 に戻る。

『……』
「さらに、 4 のところで、 IndexA と IndexB のどちらかが配列を超えて
いた場合の処理が入るから」

 1.インデックスナンバー IndexA と IndexB を作成して 0 をセットする。
 2. IndexA が上の配列を超えていたら、「結果」に「下」をセットして  へ。
 3. IndexB が下の配列を超えていたら、「結果」に「上」をセットして  へ。
 4.上の配列の IndexA の値を取得する。
 5.下の配列の IndexB の値を取得する。
 6. 4 と 5 を比較する。
 7. 6 の結果、 4 が小さければ「上」を「結果」にセットする。
 8. 6 の結果、 5 が小さければ「下」を「結果」にセットする。
 8.「結果」の側の値を、マージ先の IndexA + IndexB に書き込む。
 9.「結果」が「上」なら IndexA + 1 する。
10.「結果」が「下」なら IndexB + 1 する。
11. IndexA と IndexB 両方とも配列のサイズを超えていたら終了。
12. それ以外は 2 に戻る。

『げげげ！　こんなの無理！』
「アルゴリズムを作る、ひいてはプログラムを組むっていうことは、こうい
うことができなきゃいけないってことなんです」
『これってかなり大変……』
「しかもこれ、プログラムとは違うでしょ」
『そういえば……〈結果〉とかなかったし』
「アルゴリズムを作る、プログラムを作るっていうことは、頭の中でしてい
る処理を、こういう形で【法則を文章化する】ことなんです」
『それができないとプログラムは作れないってことね』
「そういうこと。特にアルゴリズムはね」
『特に？』
「普通のプログラムの場合」

(3,4,9)
(5,8)
　↓
[,,,,]

「こういう処理をする場合に、配列の要素数とかが固定の場合とかも結構あ
るんです」
『上が３つで下が２つ、みたいな？』
「そう。そういう場合、法則化する必要はないでしょ」
『あ……５回チェックすればいいだけなんだ』
「そういうこと。でも、アルゴリズムの場合は」
『サイズが決まってないから、どんなのでもできなきゃいけない』
「だから法則化が必要になるんです」
『むー、法則を作るコツってない？』
「ひとつは図を書くこと。フローチャートって知ってる？」
『あの四角とか菱形が並ぶヤツだよね』
「そう。あれで、最初から順に手順を書いていきます」
『最初からってつまり、１番目の要素を比較して、次に２番目の要素を比較
して、みたいに？』
「そういうこと。頭からべたに書いていきます。書き上がったら、その中身
を比較して、重複してるところとか、数が 1 ずつ増えているところとかを
探します」
『そか、そういうところは繰り返しにできるから…… for ループとかにで
きる！』
「そういうこと。【法則】ってことは何度も適用できる箇所ってことだか
ら、同じようなところをまとめるような感じにしていけばできると思うよ」
『なるほどねー。書くのはフローチャートの方がいいの？』
「図の方が、どこが似てるのかわかりやすいからね」
『確かに、文章だとなんかうっとおしい……ってゆーか、文章はどうな
の？　コードの方がわかりやすい気がするんだけど』
「その辺は場合によるかな。まず、日本語の文章で書くのと、 C++ 言語の
プログラムで書くのと、どちらが簡単か、っていうのは人それぞれだから」
『プログラマーなら絶対プログラムの方だと思うんだけど……』
「まぁね。プログラムの方がそのままコードになるし、コンパイルすること
でエラーも判るし」
『コンパイル？』
「日本語で書いたらコンパイルできないでしょ」
『そりゃそうだけど』
「コンパイルが通るっていうのも、そのアルゴリズムが間違ってないことの
証明になるからね。ただ、プログラムの方がシンプルに書けないところもあ
るから」
『たとえば？』
「配列ふたつを入れ替える、とか、コピーするとか」
『そういえば for ループでひとつずつコピーしたりしてたね』
「そういう所は日本語で書くとわかりやすいかな。それに、人に見せる場合
があるなら日本語で書く方がいいかな」
『それって、見せる相手がプログラマーじゃない場合？』
「プログラマーでも、 C++ 言語ができない場合があるでしょ」
『あ、そっか、言語が違っちゃうとダメなんだ……』
「まぁそれは日本語と英語とかっていうのもあるんだけどね。どちらにし
ろ、まずはフローチャートとかの図で考えた方がいいよ」
『まずは図ね』
「話を戻して、今回のソート編では〈アルゴリズムの考え方〉についても
ちょっとは気にとめておいてください」
『……すんごく後ろ向きな言い方ね』
「なんていうか、たとえば〈クイックソートを思いつく〉なんていうのはす
ごく大変です」
『ってゆーか絶対無理』
「ただ、クイックソートとまではいかなくても、こういうアルゴリズムを思
いつける、っていうのはすごく有利です」
『有利？』
「プログラミングの中には、こういう特殊な方法を使うことで大幅にスピー
ドアップしたりすることがあるからね」
『そういう方法を思いつかなきゃいけない……って、それってやっぱ大変だ
と思う』
「うん、大変だから、それほど気にする必要はないと思います。火美ちゃん
は研究者じゃないんだしね」
『研究者って、大学とかの？』
「そう、大学や大学院、あと企業とかでも、研究員ならアルゴリズムを考え
ることに時間を掛けられるけど、普通にプログラム作るなら」
『そんなの考えるよりプログラム作れ、と？』
「ううん、それよりも、より多くのアルゴリズムを知っておく、のが重要か
な」
『思いつくより、知っていてそれを使える方がいいってことね』
「そういうこと」
『……ならそのより多くのアルゴリズムっていうの、教えてよ』
「う”。まぁそれは他のサイトでも見てください」
『うわぁ……』

/*
    Preview Next Story!
*/
『ソート編の次は？』
「日時」
『日にちと時間……楽勝ね』
「ばかもーん！！」
『？？？？？』
「日時を笑う者は、日時に泣く！」
『というわけで次回』
＜ Version 13.22 最強の敵・日時 ＞
「につづく！」
『そんなに強敵なの……？』
「強敵そうに見えないから、凶悪」
『凶悪！！？』