Pythonでは、並べ替えアルゴリズムを挿入する簡単な分析とコードの例を使用します。
問題の説明
ランダムに並べられた数字のセットを小さい順に並べ直します。
アルゴリズムを挿入
行列から数字を取るたびに、既存の数値と比較して適切な位置を挿入します。
このように繰り返しても、既存の数字は順番に並べられ、数字が取り終わるまで並べられます。すなわち、並べ替えが成功します。
これはトランプをする時のカードの状況に似ています。
一つ目の条件:手札の順番を保つのが正しいです。
第二の条件:新しいカードを捕るたびに順番に手札の中間に挿入します。
この二つは変わらないようにしてください。何枚かの札を握っても最後の手の札は順番に並べられます。
Python実現:
別のバージョン:
ランダムに並べられた数字のセットを小さい順に並べ直します。
アルゴリズムを挿入
行列から数字を取るたびに、既存の数値と比較して適切な位置を挿入します。
このように繰り返しても、既存の数字は順番に並べられ、数字が取り終わるまで並べられます。すなわち、並べ替えが成功します。
これはトランプをする時のカードの状況に似ています。
一つ目の条件:手札の順番を保つのが正しいです。
第二の条件:新しいカードを捕るたびに順番に手札の中間に挿入します。
この二つは変わらないようにしてください。何枚かの札を握っても最後の手の札は順番に並べられます。
Python実現:
def insertion_sort(n):
if len(n) == 1:
return n
b = insertion_sort(n[1:])
m = len(b)
for i in range(m):
if n[0] <= b[i]:
return b[:i]+[n[0]]+b[i:]
return b + [n[0]]
別のバージョン:
def insertion_sort(lst):
if len(lst) == 1:
return lst
for i in xrange(1, len(lst)):
temp = lst[i]
j = i - 1
while j >= 0 and temp < lst[j]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = temp
return lst