Version 13.07
最も簡単なソート

「今回はまず、一番簡単で基本的なソートについて紹介します」
『やっぱ簡単だけあって遅いの？』
「ソートの中では一番遅いかも。だからこれを使うことはないんだけど、こ
の例で説明するとわかりやすいからね」
『はーい』
「じゃあ、まずは概念から」

4 9 3 5 8 

「これを並べ替えます」
『こうなるよね』

3 4 5 8 9 

「今の、どういうふうにした？」
『ん？　まず 3 が一番小さいから一番上に持ってきて』
「っていうふうにしたよね。それが一番基本的なアルゴリズム」
『？　でもさ、それ以外ってあるの？　それしかないような』
「僕らは、これを〈面〉で見るから、一瞬でどれが一番小さい数かわかるん
だけど、コンピューターの場合、全部ひとつひとつ見ていかなきゃいけない
でしょ」
『一度見たらいいんじゃない？』
「その見たのを記憶する、っていうのがコンピューターで言えば配列に入れ
ることなんだから」
『あ、それをまたひとつひとつ見なきゃいけないんだ……』
「だから、コンピューターのアルゴリズムは、この数字ひとつひとつをいち
いち見なきゃいけないんです」
『めんどくさー』
「だから色々方法がある、ってところかな。さて、さっき言ったように、基
本的には〈一番小さいのを見つける〉っていうことから始めるんだけど、そ
の際の方法にはいくつかあります」
『そだね、全部まず見て、小さいの取り出して取っておく、とか』
「そう。でも、その〈取っておく〉ってのが実はちょっと面倒なんです」
『なんで？』
「たとえば、２回〈小さいのを見つける〉をすると、こうなるでしょ」

9 5 8 
3 4

「こうすると、配列がもうひとつ必要になるんです」
『そっか、小さいのを入れとく配列も必要になるんだ……』
「そうすると new とか必要で面倒なんだよね。そこで、それを解決する方
法のひとつとして、元々の配列の端に入れておく、っていう方法がありま
す」
『端？』
「たとえば、小さいのふたつを頭のところに入れておくんです」

3 4 9 5 8 

「配列の要素の数はソート前と後で変わらないから、小さいのふたつを入れ
ておけるんです」
『でもこれだと、小さいのって取ったのもソートしちゃうんじゃない？』
「それを避けるために、どこまでがソート済みで、どこまでがまだソートし
てないか、っていうのを取っておく必要があります」
『それちょっと面倒そう』
「そうでもないよ。今のソートのやり方で全課程見てみればわかるかな」

4 9 3 5 8 
3*4 9 5 8
3 4*9 5 8
3 4 5*9 8
3 4 5 8*9
3 4 5 8 9

「 * の左側は〈一番小さいの〉で抜き出したもの、右側はまだ抜き出して
ないもの」
『この * の位置を憶えておくんだよね』
「でも実は憶える必要はないんです。なぜかっていうと、抜き出すたびに 
1 増えるだけだから。だから〈今何回目か〉だけわかればいいんです」
『そか、絶対に 1 ずつしか増えないからそれを利用すればいいんだ』
「１回目は５つ、２回目は４つ、っていう感じに減らしていけばいいしだけ
だからね。それともうひとつ、〈一番小さいの〉の取っておく方法」
『ん？　変数に入れておけばいいんじゃないの？』
「それだとちょっと面倒なんだよね。最初の」

4 9 3 5 8 

「を右から見ていって〈一番小さいの〉を持っておいて、それを左端に入れ
ると」

3 4 9 5 8

「になるわけだけど、これだと〈一番ちいさい数〉＝ 3 がどこにあるのか
っていうのを憶えておかないといけないんです」
『？』
「右から見ていって最後まで見たら〈 3 が一番小さい数字だった〉ってこ
とがわかるでしょ。でも、それがわかったあと、その 3 をまた探し出して
一番左端と入れ替える、っていうのは」
『二度手間だね。じゃあ配列の番号取っておけばいいんじゃない？』
「それも方法のひとつだけど、もう少し簡単な方法があります。それは、右
から見ていくときに、小さい数字があったらそれを左に持って行く方法」
『？』

4 9 3 5 8 
      ^ ^

「まず ^ がついてるものを比較します」
『 5 の方が小さいね』
「左側が小さいときには何もしないで、次を見ます」

4 9 3 5 8 
    ^ ^

『これも 3 の方が小さいね』

4 9 3 5 8 
  ^ ^

『これは 3 の方が小さいね』
「これは右側の方が小さいでしょ。そう言うときにはふたつの数を入れ替え
ます」

4 3 9 5 8 

『入れ替わった』
「で、次へ」

4 3 9 5 8 
^ ^

『これも 3 の方が小さいから入れ替えるの？』
「そう、だから」

3 4 9 5 8 

「になります」
『……あ、もしかして一番数が左端に来てる？』
「そういうこと。〈小さい数があったら入れ替えて左に持ってくる〉ってこ
とは、〈右側はそれまでの一番小さな数〉ってこと」

4 9 3 5 8 
  ^ ^

「って比較した時の右側の数字、 5 は、それまでで一番小さい数字。そう
なるように、右の方が小さい数だったら入れ替えるわけ」

4 3 9 5 8 

「そうすると、次に移ったとき」

4 3 9 5 8 
^ ^

「このときも、右側の数は」
『それまでで一番小さい 3 ってわけね』
「で、これを最後まで繰り返すと、自動的に」

3 4 9 5 8 

「というふうに一番小さな数が一番左端に来ます」
『おー』
「でもこれは〈一番小さな数〉を見つけただけ。次は〈二番目に小さな数〉
を探します」

3 4 9 5 8 
      ^ ^

『これは左の方が小さいからそのままね』

3 4 9 5 8 
    ^ ^

『これは右の方が小さいから入れ替えね』

3 4 5 9 8 
  ^ ^

『これは左の方が小さいからそのまま』
「で、ここで終わり」
『え、もう１個あるんじゃない？』
「さっき言ったでしょ、左端は〈小さい数を入れておくところ〉って」
『あ、そか、ここがそうなってるんだ……』
「だから、ここで終わり。１周するごと 1 減るから。で、３週目は」

3 4 5 9 8 
      ^ ^

『これは入れ替えね』

3 4 5 8 9 
    ^ ^

『これはそのまま。で、ここまでだよね』
「そう、さっきのひとつ手前だからね」
『４周目っと』

3 4 5 8 9 
      ^ ^

『これはそのまま。……あれ？　これで終わり？』
「そう。ソートはこれで完了」
『こうして追っていけば簡単ね』
「まぁそれをコードに落とすのが大変なんだけど」
『げげ』
「ちなみに今回の方法は【バブルソート】って言います」
『バブル？　泡？』
「そう。縦に並べると、小さい数が上に昇っていくでしょ」
『それが泡っぽい？』
「そういうこと」

/*
    Preview Next Story!
*/
『なんか聞いてただけだった……』
「アルゴリズムを１から考えるなんて大変だもの」
『とりあえずは聞くだけでいい？』
「そういうのが積み重なっていけば、作れるようになるから」
『ホントかなー』
「というわけで次回」
＜ Version 13.08 バブルソートのコーディング ＞
『につづく！』
「何を学ぶのも最初はマネから！」
『なんかビミョーに嘘くさい……』