【Python基礎講座6】基本情報技術者試験対策 / 挿入ソート(Insertion Sort) / ソートアルゴリズムの解説

挿入ソートとは

挿入ソートはソートアルゴリズムの1つです。
(ソートアルゴリズムの意味については、前回の「ソートアルゴリズムとは」で説明しています。)

名前の通りですが、挿入ソートは整列済みのデータに未整列のデータを挿入することでデータをソートするアルゴリズムです。
実際にソートの流れを見ながらのほうが分かりやすいと思いますので、[3, 8, 1, 2]を昇順にソートしながら挿入ソートのアルゴリズムを理解していきましょう。

挿入ソートでは、まず先頭の要素を整列済みと考えます。
整列済みのデータは[3]となり、未整列のデータは[8, 1, 2]です。

ここから未整列のデータを整列済みのデータに挿入していきます。
まずは未整列のデータの先頭にある8を整列済みのデータに挿入します。

挿入場所は以下の操作を繰り返すことで決めます。
まず整列済みのデータと未整列のデータの先頭を比較し、

  • 整列済みのデータの方が大きい場合は、一つ前の整列済みデータと未整列のデータを比較する。
  • 整列済みのデータの方が小さい場合は、整列済みデータの後ろに未整列のデータを挿入する。
  • もし比較する整列済みデータが存在しない(先頭まできた)時は未整列のデータを先頭に挿入する。

この操作を整列済みのデータの末尾から始めます。
まず整列済みのデータの末尾である3と未整列のデータの先頭である8を比較します。

整列済みのデータの方が小さいので、整列済みデータの後ろに挿入します。

これで整列済みのデータは[3, 8]となり、未整列のデータは[1, 2]です。
次は未整列のデータの先頭にある1を整列済みのデータに挿入します。

まず整列済みのデータの末尾である8と未整列のデータの先頭である1を比較します。

整列済みのデータの方が大きいので、一つ前の整列済みデータ3と比較します。

整列済みのデータの方が大きいので、一つ前の整列済みデータと比較します。
しかし整列済みデータ3より前にデータはありません。
比較する整列済みデータがなくなったため、先頭に挿入します。

これで整列済みのデータは[1, 3, 8]となり、未整列のデータは[2]です。
次は未整列のデータの先頭にある2を整列済みのデータに挿入します。

まず整列済みのデータの末尾である8と未整列のデータの先頭である2を比較します。

整列済みのデータの方が大きいので、一つ前の整列済みデータ3と比較します。

整列済みのデータの方が大きいので、一つ前の整列済みデータ1と比較します。

整列済みのデータの方が小さいので、整列済みデータの後ろに未整列のデータを挿入します。

これで整列済みのデータは[1, 2, 3, 8]となり、全てのデータをソートすることができました。

このように整列済みのデータに未整列のデータを挿入することでデータをソートするアルゴリズムを挿入ソートといいます。

コード

コードにするとこのようになります。
1行ずつ確認していきましょう。

def insertion_sort(data):
    length = len(data)
    for index in range(1, length):
        current_val = data[index]
        prev_index = index - 1

        while prev_index >= 0 and data[prev_index] > current_val:
            data[prev_index + 1] = data[prev_index]
            prev_index = prev_index - 1

        data[prev_index + 1] = current_val

if __name__ == '__main__':
    data = [3, 8, 1, 2, -1, -10, 4, 2]
    insertion_sort(data)
    print(data)

コード解説

1行目

まず1行目で挿入ソートを実行するinsertion_sortメソッドを定義します。
引数にソートしたいデータ(data)を受けとります。

2行目

2行目でソートしたいデータの数をlengthに入れています。
なぜデータの数が必要か考えていきましょう。
先ほど[3, 8, 1, 2]を昇順でソートした操作をまとめてみます。

  1. 先頭の要素3を整列済みとする。
    この時点で整列済みのデータは[3]、未整列のデータは[8, 1, 2]。
  2. 未整列のデータの先頭である8を整列済みデータに挿入する。
    この時点で整列済みのデータは[3, 8]、未整列のデータは[1, 2]。
  3. 未整列のデータの先頭である1を整列済みデータに挿入する。
    この時点で整列済みのデータは[1, 3, 8]、未整列のデータは[2]。
  4. 未整列のデータの先頭である2を整列済みデータに挿入する。
    この時点で整列済みのデータは[1, 2, 3, 8]となり、全てのデータのソートが完了。

操作1は先頭の要素を整列済みとしただけでソートは行っていません。
実際にソートしているのは操作2~4ですので、[3, 8, 1, 2]のデータをソートするには3回の操作が必要となります。
つまり、4個のデータをソートするには3回の操作が必要です。

ではデータが[3, 8, 1, 2, 6]の場合は何回の操作が必要でしょうか?
この場合も同じように操作をまとめてみます。

  1. 先頭の要素3を整列済みとする。
    整列済みのデータは[3]、未整列のデータは[8, 1, 2, 6]となる。
  2. 未整列のデータの先頭である8を整列済みデータに挿入する。
    整列済みのデータは[3, 8]、未整列のデータは[1, 2, 6]となる。
  3. 未整列のデータの先頭である1を整列済みデータに挿入する。
    整列済みのデータは[1, 3, 8]、未整列のデータは[2, 6]となる。
  4. 未整列のデータの先頭である2を整列済みデータに挿入する。
    整列済みのデータは[1, 2, 3, 8]、未整列のデータは[6]となる。
  5. 未整列のデータの先頭である6を整列済みデータに挿入する。
    整列済みのデータは[1, 2, 3, 6, 8 ]となり、全てのデータのソートが完了。

今回も操作1は先頭の要素を整列済みとしただけでソートは行っていません。
実際にソートしているのは操作2~5ですので、[3, 8, 1, 2, 6]のデータをソートするには4回の操作が必要となります。
つまり、5個のデータをソートするには4回の操作が必要です。

もうお分かりかもしれませんが、挿入ソートでは先頭以外の要素を1つずつ挿入して整列済みとするため、先頭以外のデータの要素数がソートする回数となります。
つまりソートしたいデータの要素数とソートする回数の関係は、「ソートする回数 = ソートしたいデータの要素数 – 1」と表せます。

このように、必要な操作の回数を知るためにデータの要素数が必要なので、2行目でデータの要素数をlengthに入れています。

3行目

次に3行目でrange(1, length)の範囲でループし、操作が何回目にあたるかを index に入れています。
例えばPythonでは for index in range(1, 5):と書くことで index は1, 2, 3, 4の値をとり、4回ループします。
先ほどみたようにループの回数(操作の回数)はデータの要素数 – 1回となっています。

4行目

4行目はcurrent_val = data[index]です。
indexには1回目の操作なら1、2回目の操作なら2のように何回目の操作かを表す値が入っています。
1回目の操作ではcurrent_val =data[1]となり、2回目の操作ならcurrent_val =data[2]となります。
つまりdata[index]はこれからソートするデータを表し、その値をcurrent_valに入れています。
current_valは以下の図でいうと「これから整列する要素」を表しています。

5~11行目

5~11行目は先ほど見た以下の操作を表しています。

  • 整列済みのデータの方が大きい場合は、一つ前の整列済みデータと未整列のデータを比較する。
  • 整列済みのデータの方が小さい場合は、整列済みデータの後ろに未整列のデータを挿入する。
  • もし比較する整列済みデータが存在しない(先頭まできた)時は未整列のデータを先頭に挿入する。

詳しく見ていきましょう。

5行目のprev_indexは比較する整列済みデータの位置を表します。
最初に比較するのは整列済みデータの末尾でした。
整列済みデータの末尾はこれから整列するデータの1つ手前です。
そのためprev_index = index – 1としています。

また、比較する整列済みデータの位置は比較するたびに先頭に向かって1つ進んでいきましたね。
つまり比較するたびにprev_index = prev_index – 1 となります。
コードが少し前後しますが、これは9行目で行っています。

次は7行目のwhile文ですが、説明の関係で先ほど見た以下の操作に番号をふり、上から条件1とします。

  1. 整列済みのデータの方が大きい場合は、一つ前の整列済みデータと未整列のデータを比較する。
  2. 整列済みのデータの方が小さい場合は、整列済みデータの後ろに未整列のデータを挿入する。
  3. もし比較する整列済みデータが存在しない(先頭まできた)時は未整列のデータを先頭に挿入する。

結論からいうと、7行目のwhile文の処理は条件1の時だけ入るようになっています。

while文が何を意味するかを前半と後半に分けて説明していきます。
まず前半のprev_index >= 0ですが、prev_indexは比較する整列済みデータの位置を表していました。
データの位置は以下のように先頭が0から始まります。

先頭データの位置が0ですから、データの位置が0より小さいというのは先頭より前になります。
比較する整列済みデータが先頭よりも前というのは、比較する整列済みデータがないということです。
これは条件3「もし比較する整列済みデータが存在しない(先頭まできた)時」です。
つまり、prev_index >= 0とすることで比較する整列済みデータが存在する場合のみwhileの処理が行われるようにしており、言い換えると条件3の時にはwhileの処理が行われないようになります。

後半のdata[prev_index] > current_valは、整列済みのデータの方が大きい場合を表しています。
つまり条件2の整列済みのデータの方が小さい場合はwhileの処理が行われないようになります。

まとめると、while prev_index >= 0 and data[prev_index] > current_valとすることで条件1の場合のみwhileの処理が行われ、条件2と3はwhileの処理が行われなくなります。

これによりwhileの中にある8行目と9行目の処理は条件1の時に実行され、whileの外にある11行目の処理は条件2と3の時に実行されるということが分かります。

9行目は先ほどprev_indexの時に説明した「比較する整列済みデータの位置は比較するたびに先頭に向かって1つ前に進む」でした。

では8行目は何をしているでしょうか。
コードを見ると整列済みデータを1つ後ろにずらしています。
まず概要を理解してほしいため先ほどの説明では省きましたが、挿入ソートでは比較した後に整列済みデータを1つ後ろにずらす操作が必要になります。
理由は挿入する場所を空けるためです。
図で見た方がイメージしやすいので図で見てみましょう。

例えば整列済みのデータが[1, 3, 8]で未整列のデータが[2]の時にどのように2が整列済みデータに挿入されるかを図で見てみます。
今回はデータの位置が分かりやすいように、それぞれのデータの位置に番号をふっています。

まず整列済みのデータの末尾である8と未整列のデータの先頭である2を比較します。

整列済みのデータの方が大きいので、一つ前の整列済みデータ3と比較するのですが、その前に8を後方に一つずらします。

次に整列済みのデータ3と比較します。

整列済みのデータの方が大きいので、3を後方に一つずらします。

次に整列済みのデータ1と比較します。

整列済みのデータの方が小さいので、整列済みデータの後ろに未整列のデータ2を挿入します。
先ほど3を後方にずらしたことで[1]が空いているため、空きスペースに挿入することができます。

今見たように挿入するためのスペースを空けるため、8行目で整列済みデータを後方にずらしています。

最後の11行目ですが、条件2と3の共通処理でした。
条件2と3で共通となる処理は未整列データの挿入ですね。
prev_indexは比較した整列済みデータの位置を表しているため、prev_index + 1で1つ後ろの空きスペースの位置を表します。
つまり空きスペースのデータ(data[prev_index + 1])に未整列のデータ(current_val)を入れています。

実行結果

コードを実行して昇順にソートされることを確認しましょう。

ちゃんと昇順にソートされていますね。

計算量

最後にデータ数をNとした時の計算量をO記法で表現してみましょう。
(O記法については以前学んだO記法の説明を参考にしてください。)

挿入ソートのコードの中で、ソートするデータ数によって計算量が変わるところはどこでしょうか。

まず3行目のfor index in range(1, length)ですね。
forでループしており、ループ数はlengthで決まります。
lengthには2行目でデータ数(len(data))を入れているため、ループ数はデータ数によって変わります。

もう一か所あります。
それは7行目のwhile文です。
挿入ソートのアルゴリズムを少し振り返ると、未整列のデータを整列済みデータと繰り返し比較し、先頭まで繰り返すか、もしくは整列済みデータよりも未整列のデータの方が大きければ繰り返しを終了しました。
もし1度目の比較で整列済みデータよりも未整列のデータの方が大きければ繰り返しは1回だけで済みますが、整列済みデータよりも未整列のデータの方が小さい場合が続けば、操作は先頭まで繰り返されます。
この先頭まで比較を繰り返す場合を考えると、データ数がNなら比較する回数はN – 1回となります。
つまりデータ数Nが増えれば増えるほど操作の回数も増えるため、操作の回数はデータ数に比例していると考えられます。

ここまでをまとめると、計算量がデータ数に比例するのは3行目のfor文と7行目のwhile文の2か所であり、while文はfor文の中にネストしています。
(このネストした計算量の説明はバブルソートの計算量のところで解説しています。
もしよく分からなければそちらを参考にしてみてください。)

つまり挿入ソートの計算量はO(N) x O(N) = O(N2)となります。

最後に

以上、第6回目は挿入ソートについてでした。
基本のアルゴリズムですので、しっかり理解しておきましょう。

以下の記事で他のソートアルゴリズムについても解説しています。
興味があれば読んでみてください。

以下では探索アルゴリズムを解説しています。
こちらも基本のアルゴリズムとなりますので、しっかり理解しておきましょう。

分かりにくいところや「もっとこうしてほしい」などのご意見がありましたら、ツイッターから連絡いただけると幸いです。
質問に関してもお気軽にお問い合わせください。

私は独学で以下の本からPythonを学びました。
上が初級者向けで下が中級者向けといった感じです。
気が向いたら立ち読みでもしてみてください。

コメント

タイトルとURLをコピーしました