【16日目】挿入ソート

挿入ソートとは何だろうか？

まずは例を挙げよう。7並べをみんなでしているとしよう。手札が配られ、全員に行き渡ったら手札を確認しまずはどうするだろうか？

配られて最初にするのはトランプを小さい順もしくは大きい順に並べ替えることではないだろうか？

小さい数を見つけたら左へとやっていくのではないだろうか？では、これを少しわかりやすくして考えたてみよう。

左側に1枚だけもち、右側にはバラバラな残りのカードを持っているとしよう。

左側のカードをどの時点でも、小さい順に並んでいるようにしておきたい。そこで右側の1番左側のカードを左に持っていく。

その際に左側のカードと比較していく。どちらが大きかだけである。大きければ左手の右側に、小さければ左手の左側にとしていく。

左手にカードが移ったら残りのカードも同じように繰り返していく。左手の左側に比較するカードよりも小さいものが大きいものがなくなるまで繰り返す。

そうこうしていると右手のカードはなくなり、左手に小さい順に並んだ手札が出来上がる。

これが挿入ソートである。とてもシンプルなものである。

アルゴリズムは数学を使い厳密に定義することもできるが、実際は数学を使わないで図や実際のものを使うことで理解することができる。

わからなければ手を動かす。1個からどんどんと増やしていき考えていくのもいい。

図や実物のもので十分に遊んでみる。インテリぶったアルゴリズム考案者(知らんけど)の粗探しをするように、批判的な目でみる。

☆批判的な目でみるのが難しい人へ
批判的な目線で見なさい！疑ってかかりなさいとよく言われるが実際すごい難しい。

相手は本を書くほどその分野に精通した人だろうし、アルゴリズムの本とか数学の分野だからなおのこと小難しく書かれている。

「厳密には、むにゃむにゃ...」
「この過程が成り立つことによりふがふが...」

等小難しいことを専門用語をふんだんに使って襲いかかってくる。そんな言い方されると偉いお方のお言葉だーとなってしまう。

正直疑うなど難しい。なので自分がやっているくだらないアイディアは説明を脳内で関西弁のおっさんに変換すること。

「よーきーときや、今から小難しい話すんで」
「こうやったらこうなるやん、そうするとこれも成り立つやろ？せやろ？そしたらこうや」

こうやってしまえば怪しいおっさんの説明だからこっちも「ほんまかいな」「あほくさ、絶対嘘やわ」と疑うハードルは下がる。

ちなみに自分がイメージしているおっさんは駅構内で若者を見つけては、本当かどうか疑わしいような過去の栄光を自慢しながら、マウントを取ろうとするおっさんである。

「俺は陸上で国体にも出たことがあるんやぞ」と言ってくるタイプのおっさんである。

ぜひ、実践してみてください。