プログラミングの世界には、いろいろなソートアルゴリズムがある。バブルソート、選択ソート、挿入ソート、マージソート、ヒープソートなどである。
それぞれのコードの書き方の具体例はインターネット上にあふれているので、知りたいときは検索すれば済む。しかし、コードを示されて具体的に説明されてもいまいち理解できないという場合も多いだろう。
そこで、今回は挿入ソートについて理解するために、抽象的な観点から説明してみたい。
挿入ソートの基本的な流れは次の通りだ。
配列がソート済みの部分と未ソートの部分に分けられていると考え、未ソート部分の要素をソート済み部分の適切な位置に挿入していく。
おそらく実際のコードでは二重ループを使っているはずであり、外側は未ソート部分走査ループで、内側はソート済み部分走査ループとなっている。
この二重ループを使って、未ソート部分から要素をひとつ取り出し、ソート済み部分を走査していって適切な位置に挿入すればいいのだ。
適切な位置に挿入するときは、バブルソートのように1つずつ交換して目的の要素を移動させるのではなく、ソート済み部分をひとつずらしていって、適切な位置が見つかったら一気にそこに置くようにする。こうすることで、効率化が図られている。
ソート済み部分と未ソート部分。このキーワードを頭に入れながらコードを読めば、挿入ソートを理解できるだろう。
プログラミングを理解するコツは、抽象と具体を何度も行き来することだ。抽象的に考えて理解できなければ具体的に考えてみる。具体的に考えてわからなければ抽象的に考えてみる。この繰り返しによって、理解できるようになるのだ。
