【アルゴリズムの勉強】Pythonで挿入ソートを書いてみた
学習エントリ。
Pythonで挿入ソートを実装する。
挿入ソートってなんぞ
挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。
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に条件を複数追加