インサーション（挿入）ソートについての2つ目の記事です。前回の記事でインサーション（挿入）ソートとは？と取り上げて、ソート方法の考え方を書きました。今回は実際に、Pythonでインサーションソートを書いてみたいと思います。
インサーション（挿入）ソートのおさらい（ちょっとだけ）
詳細は前回の記事に譲りますが、ソートとは、下図のようにバラバラに並んだカードなどを小さい順（昇順）もしくは大きい順（降順）に並べる方法でした。
そのソートの方法（アルゴリズム）には種類があり、その中の１つがインサーション（挿入）ソートでした。
インサーションソートはバラバラのものを順に正しい位置に挿入して、順番に並べていく方法です。実際のアルゴリズムではバラバラのもの（上図、青枠のバラバラのもの）の左側から大小を比較することにより、正しい位置に並べ替えていきます。
実際のアルゴリズム（プログラミング）では…（昇順の場合）（with Python）
まず、上記バラバラのカードを変数Cardsのリストに格納します。
Cards = [4,2,5,1,3]Step1：一番左端のカード（4のカード）
左端のカードはそのままにします。
コードでは、バラバラのままのカードのまとまり（青枠内）の一番左をリストCardsに格納していきます。
#Step1
Cards = [4,2,5,1,3]
Cards[0] = Cards[0]Step2：左から2番目のカード（2のカード）
Step2-1：2と4のカードの比較
次に、左から2番目のカードを取って、まず青枠の外から出します。そして、外に出したカード（2のカード）とその左横のカード（4のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回の場合は4より2の方が小さいので、4のカードを右横に移動させます。
この操作をコードに書き換えます。まず、2のカードを青枠の外に出すところは別の変数cardに格納する事で対応します。
続いて、2と4を比較して、4の方が大きいので、4のカードを右にひとつずらすところはリストCardsの各番号に直接代入することで対応します。ここまでをコードにします
#Step1
Cards = [4,2,5,1,3]
Cards[0] = Cards[0]
#Step2-1
card = Cards[1]
if Cards[0] > card:
Cards[1] = Cards[0]Step2-2：取ったカードを青枠内に戻す
次に、もともとあった4のカードは一番左のカードでそれより左はないので、青枠の外に出していた2のカードを空いた箇所に戻します。
Step2-2を実装する為にリストCards[0]に変数cardの値を代入します。
#Step1
Cards = [4,2,5,1,3]
Cards[0] = Cards[0]
#Step2-1
card = Cards[1]
if Cards[0] > card:
Cards[1] = Cards[0]
#Step2-2
Cards[0] = cardここまでを実行すると、以下のリストが返ってきます。
[2, 4, 5, 1, 3]となっています。
※Pythonのリストは0から始まる事に注意です。
Step3：左から3番目のカード（5のカード）
Step3-1：5と4のカードの比較
次に、左から3番目のカードを取って、青枠の外に出します。そして、外に出したカード（2のカード）とその左横のカード（4のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回の場合は5が4より大きいので、そのままになります。
Step3-1をコードにすると、以下のようになります。まず左から3番目の5のカード（Cards[2]）を青枠から出すために変数cardに代入します。その次に、5と4の比較をする為に、左から3番目と2番目を比較します。
今回は実施されませんが、左から3番目と2番目を比較して3番目のカードの方が小さかったら、更に左から3番目と1番目を比較する操作が必要なので8～11行目のコードも書いています。
#Step1と2の記載省略
#Step3-1
card = Cards[2]
if Cards[1] > card:
Cards[2] = Cards[1]
#もし、Cards[1]>cardがTrueだったら、以下も実行。
#今回は4 > 5となり（False）となり、実行されない。
if Cards[0] > card:
Cards[1] = Cards[0]
Cards[0] = cardStep3-2：取ったカードを青枠内に戻す
次に、青枠の外に出していた5のカードを空いた箇所に戻します。今回は5のカードを外に出してから、青枠内での移動がなかったので、そのまま元に戻します。
ここは、4行目のif文の条件分岐で対応できるので追加のコードは書いていません。
Step4：左から4番目のカード（1のカード）
Step4-1：1と5のカードの比較
次に、左から4番目のカードを取って、青枠の外に出します。そして、外に出したカード（1のカード）とその左横のカード（5のカード）を比べます。取ったカードの方が大きかったら、そのまま。取ったカードの方が小さかったら、左横のカードを右横に移動させます。今回は5が1より大きいので、5を右に1つずらします。
ここの部分をコードに書くと、以下のようになります。これまで同様、1のカードを青枠外に出すために変数cardに代入します。その後、左から3番目のカード（5のカード：Cards[2]）と比較して、左のカードの方が大きかったら、元々1のあった場所へ代入することにより、右に1つずらすことを実現します。
#Step1~3は記載省略
#Step4-1
card = Cards[3]
if Cards[2] > card:
Cards[3] = Cards[2]Step4-2：4と1のカードの比較
次に青枠の外に出したカード（1のカード）と5のカードの左横にあった4のカードを比較します。外に出したカードの方が大きかったら、そのまま。外に出したカードの方が小さかったら、青枠内のカードを右横に移動させます。今回は4が1より大きいので、4を右に1つずらします。
この部分をコードに書くと、次のようになります。Step4-1でTrue（右に1つずらすことが実施）の場合は続いて、上記のように4と1の比較をしないといけません。その為、if文のネスト（入れ子）で対応します。あとのコードはリストのCardsの番号が変わっただけで、考え方は変わりません。
#Step1~3は省略
#Step4-1
card = Cards[3]
if Cards[2] > card:
Cards[3] = Cards[2]
#Step4-2
if Cards[1] > card:
Cards[2] = Cards[1]
Step4-3：2と1のカードの比較
次に青枠の外に出したカード（1のカード）と4のカードの左横にあった2のカードを比較します。外に出したカードの方が大きかったら、そのまま。外に出したカードの方が小さかったら、青枠内のカードを右横に移動させます。今回は2が1より大きいので、2を右に1つずらします。
この部分をコードで書くと、以下のようになります。Step4-2同様に、Step4-2がTrue（右に1つずらすことが実施）の場合は続いて、上記のように2と1の比較をしないといけません。その為、更にif文のネスト（入れ子）で対応します。
#Step1~3記載省略
#Step4-1
card = Cards[3]
if Cards[2] > card:
Cards[3] = Cards[2]
#Step4-2
if Cards[1] > card:
Cards[2] = Cards[1]
#Step4-3
if Cards[0] > card:
Cards[1] = Cards[0]Step4-4：取ったカードを青枠内に戻す
次に、もともとあった2のカードは一番左のカードでそれより左はないので、青枠の外に出していた1のカードを空いた箇所に戻します。
Step4-1～4-3のコードを書くと以下のようになります。Step4-2はStep4-1で入れ替えが発生しここをコードで書くと、以下のようになります。今回は一番左までいったので、10行目の部分だけで実現はできますが、未知のリストに対してはネストとなったif文のどこまで実行されるかわからないので、各if文のブロックに追記します。（5、10、15行目）
#Step4-1
card = Cards[3]
if Cards[2] > card:
Cards[3] = Cards[2]
Cards[2] = card #青枠内に戻す
#Step4-2
if Cards[1] > card:
Cards[2] = Cards[1]
Cards[1] = card #青枠内に戻す
#Step4-3
if Cards[0] > card:
Cards[1] = Cards[0]
Cards[0] = card #青枠内に戻すStep1~4を実行すると、以下のリストに並べ変わっています。（もう少しでソートが終わる…!!!!）
[1, 2, 4, 5, 3]ここまでのコードを整理
カードが5枚なので、各工程を書いて対応できていますが、100枚や1000枚のカードを並べ替える時にとても対応できないコードになってきました。そこで、for文とwhile文を用いて、読みやすく、汎用性のあるコードに書き換えていきます。この書き換えを行うと、これ以降のコードもまとめて対応できるようになります。実際のコードは以下のようになります。
Cards = [4,2,5,1,3]
for i in range(1,len(Cards)):
j = i-1
#左から順番に数字のカードを外に出す
card = Cards[i]
#青枠の外に出したカードと左のカードとの比較を順に行う
while (j >= 0 and Cards[j] > card) :
Cards[j+1] = Cards[j]
#右にカードをずらす操作が行われた場合は
#更に左のカードと青枠の外のカードの比較が
#必要なので、jの値を1つ小さくする
j -= 1
#青枠の外に出していた数字のカードを青枠内に戻す
Cards[j+1] = card
print(Cards)
【実行結果】
[1, 2, 4, 5, 3]コード解説
forループ部分
まず、Step1の部分はカードの移動が発生しておらず、元の並び方のままで大丈夫なので、省略します。次に、Step2の部分は0番目をj番目（i-1番目）、1番目をi番目とします。これを、左から2番目（i番目）のカードをとって、3番目（i+1番目）のカードをとって…としていくために、forループを回します。青枠の外にだすためにi番目のカードを変数cardに代入します。
whileループ部分
Cards[j] > cardの部分
取ったカード（青枠の外に出したカード：card）とその左側の数字（Cards[j]）を比較して、Cards[j]の方が大きい時はCards[j]をひとつ右にずらします。そして、移動が実行された時は更にj-1番目と変数cardについても同じように数字の大小を比較して、Card[j-1]の方が変数cardよりも大きい時はCard[j-1]を右にずらすことを実行して、j-2番目、変数cardの数字を比較して…とwhileループで繰り返します。
whileループ内でカードが右に1つずれる事が実行された時には、jの値が1つ小さくなったカードについても変数cardと比較する事が実施されないといけないので、whileループの最後でjの値を1つ小さくしています。
j >= 0の部分
jの数はwhileループが回るたびに1つずつ小さくなってしまいますが、jの最小値は0（リストは0から始まるので）なので、jが0より小さくなるとリスト番号が割り振られていない値になってしまい、エラーが返されます。その為、jが0より小さくならない為に、whileループが回る条件をj >= 0とします。
降順にする場合（インサーションソートwith Python）
これまでのコードをたった1か所（>を<に）変えるだけで完成できて、
（昇順）Cards[j] > card
だった箇所を
（降順）Cards[j] < card
とするだけでできます。
Cards = [4,2,5,1,3]
for i in range(1,len(Cards)):
j = i-1
#左から順番に数字のカードを外に出す
card = Cards[i]
#青枠の外に出したカードと左のカードとの比較を順に行う
while (j >= 0 and Cards[j] < card) :
Cards[j+1] = Cards[j]
#右にカードをずらす操作が行われた場合は
#更に左のカードと青枠の外のカードの比較が
#必要なので、jの値を1つ小さくする
j -= 1
#青枠の外に出していた数字のカードを青枠内に戻す
Cards[j+1] = card
print(Cards)
【実行結果】
[5, 4, 3, 2, 1]＊
＊
＊
コードを見ただけでは理解しにくいこともあるかと思います。そんな時には実際に自分で変数（上記であればiやj）に値を入れて、１つずつの工程を追っていくと案外すんなり理解出来たりします。デバッカーで順に追っていたり、紙に少し書きだすだけで理解しやすくなるので、理解に困った場合はオススメな方法です。
コメント