A社の佐伯さんがのらりくらりと

A社の佐伯さんがのらりくらりと。インターネットと少しだけ生活のこと。

【アルゴリズムの勉強】Pythonで挿入ソートを書いてみた

学習エントリ。

Pythonで挿入ソートを実装する。

挿入ソートってなんぞ

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def insertSort(list,order):
    for i in xrange(1,len(list)):
        j = i
        if order == ASC:
            while j > 0 and list[j] < list[j - 1]:
                list[j], list[j - 1] = list[j - 1], list[j]
                j -= 1
        elif order == DESC:
            while j > 0 and list[j] > list[j - 1]:
                list[j], list[j - 1] = list[j - 1], list[j]
                j -= 1
    return list
        

print("ASC is...")
print(insertSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(insertSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]
ポイントっぽいところ
  • xrange(1,len(list)):1からスタートする
  • iを直接使わず、jという変数で管理する(用途が異なるため)
  • 最後にjを減らしていくことで、連続して判定
  • whileに条件を複数追加