ソート（sort）とは、日本語で「並べ替える、分類する、仕分けする」などの意味があります。プログラミングでソートというと、バラバラに並んだ数字のカードを小さいものから大きいものに並べ替える（昇順）、大きいものから小さいものに並べ替える（降順）、事をいいます。プログラミングでソートをする方法（アルゴリズム）は色々あり、今回はインサーション（挿入）ソートを取り上げます。
他のソートのアルゴリズムは以下の記事を参照ください。
インサーション（挿入）ソートとは？
インサーションソート（insertion sort）とは並べ替える方法の１つで、1～5までの数字のカードがバラバラに並んでいる時に1枚ずつ選んでは、適切な箇所に割り込ませて（挿入して）、順番になるように並べます
言葉だけだと分かりにくいので、実際に図を用いて解説します。まず、最初は下図のように数字カードがバラバラに並んでいるとします（バラバラゾーン）。
これを左から順番にカードを取って、整列ゾーンに小さい順（昇順）に並べていきます。
Step1：カード4を取って整列ゾーンに
まず、4のカードを選んで整列ゾーンに並べます。この時、整列ゾーンにはカードは1枚もないので、そのまま左端に並びます。
Step2：カード2を取って整列ゾーンに
次にバラバラゾーンにある左端の2のカードを取って、整列ゾーンに並べます。2は4より小さいので4の左横に置きます。
Step3：カード5を取って整列ゾーンに
次はバラバラゾーンの左端の5のカードを取って、整列ゾーンに並べます。5は一番大きいので、整列ゾーンの右端に置きます。
Step4：カード1を取って整列ゾーンに
次はバラバラゾーンの一番左端の1のカードを取って、整列ゾーンに並べます。1は一番小さいので整列ゾーンの左端に置きます。
最終Step：カード3を取って整列ゾーンに
最後のStepはバラバラゾーンの最後のカード3を取って、整列ゾーンに並べます。3は2と4の間に割り込ませて（挿入して）、並べます。
これで綺麗に小さい順（昇順）に並びました。
実際のアルゴリズム（プログラミング）では…
実際にインサーションソートでコードを書く場合は、計算量を少なくするために、バラバラゾーンと整列ゾーンを分けずに書きます。
Step1：一番左端のカード（4のカード）
左端のカードはそのままにします。
Step2：左から2番目のカード（2のカード）
Step2-1：2と4のカードの比較
次に、左から2番目のカードを取って、まず青枠の外から出します。そして、外に出したカード（2のカード）とその左横のカード（4のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回の場合は4より2の方が小さいので、4のカードを右横に移動させます。
Step2-2：取ったカードを青枠内に戻す
次に、もともとあった4のカードは一番左のカードでそれより左はないので、青枠の外に出していた2のカードを空いた箇所に戻します。
Step3：左から3番目のカード（5のカード）
Step3-1：5と4のカードの比較
次に、左から3番目のカード次に、左から3番目のカードを取って、青枠の外に出します。そして、外に出したカード（2のカード）とその左横のカード（4のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回の場合は5が4より大きいので、そのままになります。
Step3-2：取ったカードを青枠内に戻す
次に、青枠の外に出していた5のカードを空いた箇所に戻します。今回は5のカードを外に出してから、青枠内での移動がなかったので、そのまま元に戻します。
Step4：左から4番目のカード（1のカード）
Step4-1：1と5のカードの比較
次に、左から4番目のカードを取って、青枠の外に出します。そして、外に出したカード（1のカード）とその左横のカード（5のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回は5が1より大きいので、5を右に1つずらします。
Step4-2：4と1のカードの比較
次に青枠の外に出したカード（1のカード）と5のカードの左横にあった4のカードを比較します。外に出したカードの方が大きかったら、そのまま。外に出したカードの方が小さかったら、青枠内のカードを右横に移動させます。今回は4が1より大きいので、4を右に1つずらします。
Step4-3：2と1のカードの比較
次に青枠の外に出したカード（1のカード）と4のカードの左横にあった2のカードを比較します。外に出したカードの方が大きかったら、そのまま。外に出したカードの方が小さかったら、青枠内のカードを右横に移動させます。今回は2が1より大きいので、2を右に1つずらします。
Step4-4：取ったカードを青枠内に戻す
次に、もともとあった2のカードは一番左のカードでそれより左はないので、青枠の外に出していた1のカードを空いた箇所に戻します。
Step5：左から5番目のカード（3のカード）
Step5-1：3と5のカードの比較
次に、左から5番目のカードを取って、青枠の外に出します。そして、外に出したカード（3のカード）とその左横のカード（5のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回は5が3より大きいので、5を右に1つずらします。
Step5-2：3と4のカードの比較
次に青枠の外に出したカード（3のカード）と5のカードの左横にあった4のカードを比較します。外に出したカードの方が大きかったら、そのまま。外に出したカードの方が小さかったら、青枠内のカードを右横に移動させます。今回は4が3より大きいので、4を右に1つずらします。
Step5-3：3と2のカードの比較
次に青枠の外に出したカード（3のカード）と4のカードの左横にあった2のカードを比較します。外に出したカードの方が大きかったら、そのまま。外に出したカードの方が小さかったら、青枠内のカードを右横に移動させます。今回は2が3より小さいので、そのままになります。
Step5-4：取ったカードを青枠内に戻す
次に、青枠の外に出していた3のカードを空いた箇所に戻します。
以上で並べ替えることができました。
実際にPythonでコードも書いてみました。ぜひご覧ください。
コメント