Pythonで単純挿入法(挿入ソート)を実装

アルゴリズム:単純挿入法

def insertion_sort(ilist):
for x in range(1, len(ilist)): # 0はソート済みにする
currentvalue = ilist[x] # 比較対象の値を退避
position = x # 現在のインデックスを格納
while position > 0 and currentvalue < ilist[position - 1]:
"""インデックスが0以上かつ、比較対象が1つ前の値よりも小さい場合に、ずっとループ"""
ilist[position] = ilist[position - 1] # 大きかった値を1つ上のインデックスにずらす
position -= 1 # 比較するインデックスを小さくする
ilist[position] = currentvalue # whileから抜けた時に、今のpositionに比較対象を入れる
return ilist


if __name__ == '__main__':
import random

bf_array = [x for x in range(20)]
af_array = random.sample(bf_array, len(bf_array))
print(af_array)
print('========ソート後========')
gfarray = insertion_sort(af_array)
print(gfarray)

##########結果##########

[17, 0, 2, 8, 19, 6, 16, 3, 11, 14, 7, 18, 12, 10, 13, 9, 5, 15, 1, 4]
========ソート後========
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

コメント

現在コメントはありません

新しいコメント

*
*
*

admin

こんにちは!Bicepperです。
メインはフロントですが、Python・AWS・GCPやったりと手を広げまくってます。

筋トレ歴10年目。筋トレのこともたまーに書いたりします。

Twitter Feed