Insertion Sort

Pythonで「挿入ソート（Insertion Sort）」

はじめに

ここでは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の中で取り上げられている「AOJ (Aizu Online Judge」)の問題を自分で解いた際に学んだことや、こう考えれば分かりやすいと感じたことなどを自分への整理も兼ねてまとめています。
このテキストはC++で書かれているので、私のようにpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、至らない点が多々あると思いますので、ご指摘・ご助言頂ければ喜びます。よろしくお願いします。

問題詳細

ALDS 1_1_A: Insertion Sort
挿入ソートで昇順に並べ替える問題です。
問題詳細は上記リンクをご参考ください

考え方

・先頭の要素をソート済みとする
・未ソートの部分がなくなるまで、以下の処理を繰り返す
　　1. 未ソート部分の先頭から要素を１つ取り出して、vに入れる
　　2. ソート済みの部分において、vよりも大きい要素を１つずつ移動する
　　3. 最後に空いた位置に「取り出した要素v」を挿入する

pythonコード

def InsertionSort(A, N):
    for i in range(N):
        v = A[i]       # A[i]は未ソート部分の先頭
        j = i - 1
        while j >= 0 and A[j] > v: 
            A[j+1] = A[j]  # vよりも大きい要素を一つ右に移動させる
            j -= 1     # 比較する位置を移動
        A[j+1] = v     # 空いた部分にvを入れる
        print(*A)

N = int(input())
A = list(map(int, input().split()))

InsertionSort(A, N)

ポイント

・未ソート部分の先頭の値と比較を行うのはA[j]であり、A[j]の方が大きい場合、A[j+1]にA[j]を移動させる。この時に実質空いているのはA[j]の位置であるが、これと同じタイミングでwhile内でj-1を行うため、未ソート部分の先頭を移動させる際に空いている位置はj+1になります。

まとめ

以上となります。間違いや改善点などございましたら、よろしくお願いいたします。