アルゴリズムの練習です。
挿入ソートの実装をPythonで試してみます。
例 リストにバラバラに格納されている数値を昇順にする。
同様の動作をループしていきます。
こんな感じで絵を描いてみました。
以下、実装例です。
l = [2, 1, 4, 3]
for i in range(len(l)):
tmp = l[i]
for j in range(i-1, -1, -1):
if l[j] > tmp:
l[j+1] = l[j]
l[j] = tmp
print(l)
# 出力内容
# [1, 2, 3, 4]
もっと大きな要素数で試してみます。
l = [
549,570,88,752,882,280,965,823,54,189,871,923,180,972,308,262,621,991,981,98,123,0,527,249,802,11,464,69,412,
772,630,978,454,672,781,376,575,945,519,854,719,707,368,304,921,390,140,516,359,945,676,463,990,489,76,776,
940,206,849,22,361,811,537,47,600,242,395,646,670,867,236,447,542,203,702,239,372,593,473,115,916,788,925,
636,843,613,285,964,739,372,730,468,781,19,945,192,778,57,226,350
]
for i in range(len(l)):
tmp = l[i]
for j in range(i-1, -1, -1):
if l[j] > tmp:
l[j+1] = l[j]
l[j] = tmp
print(l)
# 出力内容
# [
# 0, 11, 19, 22, 47, 54, 57, 69, 76, 88, 98, 115, 123, 140, 180, 189, 192, 203, 206, 226, 236, 239, 242, 249, 262, 280,
# 285, 304, 308, 350, 359, 361, 368, 372, 372, 376, 390, 395, 412, 447, 454, 463, 464, 468, 473, 489, 516, 519, 527,
# 537, 542, 549, 570, 575, 593, 600, 613, 621, 630, 636, 646, 670, 672, 676, 702, 707, 719, 730, 739, 752, 772, 776,
# 778, 781, 781, 788, 802, 811, 823, 843, 849, 854, 867, 871, 882, 916, 921, 923, 925, 940, 945, 945, 945, 964, 965,
# 972, 978, 981, 990, 991
# ]
本当に合っているのかどうか確認するのが目では確認できないので、以下の方法で確認しました。
l = [
549,570,88,752,882,280,965,823,54,189,871,923,180,972,308,262,621,991,981,98,123,0,527,249,802,11,464,69,412,
772,630,978,454,672,781,376,575,945,519,854,719,707,368,304,921,390,140,516,359,945,676,463,990,489,76,776,
940,206,849,22,361,811,537,47,600,242,395,646,670,867,236,447,542,203,702,239,372,593,473,115,916,788,925,
636,843,613,285,964,739,372,730,468,781,19,945,192,778,57,226,350
]
for i in range(len(l)):
tmp = l[i]
for j in range(i-1, -1, -1):
if l[j] > tmp:
l[j+1] = l[j]
l[j] = tmp
print(l)
# 出力内容
# [
# 0, 11, 19, 22, 47, 54, 57, 69, 76, 88, 98, 115, 123, 140, 180, 189, 192, 203, 206, 226, 236, 239, 242, 249, 262, 280,
# 285, 304, 308, 350, 359, 361, 368, 372, 372, 376, 390, 395, 412, 447, 454, 463, 464, 468, 473, 489, 516, 519, 527,
# 537, 542, 549, 570, 575, 593, 600, 613, 621, 630, 636, 646, 670, 672, 676, 702, 707, 719, 730, 739, 752, 772, 776,
# 778, 781, 781, 788, 802, 811, 823, 843, 849, 854, 867, 871, 882, 916, 921, 923, 925, 940, 945, 945, 945, 964, 965,
# 972, 978, 981, 990, 991
# ]
# リスト l をコピー
x_l = [
549,570,88,752,882,280,965,823,54,189,871,923,180,972,308,262,621,991,981,98,123,0,527,249,802,11,464,69,412,
772,630,978,454,672,781,376,575,945,519,854,719,707,368,304,921,390,140,516,359,945,676,463,990,489,76,776,
940,206,849,22,361,811,537,47,600,242,395,646,670,867,236,447,542,203,702,239,372,593,473,115,916,788,925,
636,843,613,285,964,739,372,730,468,781,19,945,192,778,57,226,350
]
x_l.sort()
print(l == x_l)
# 出力内容
# True
完全一致している事が確認できました。
挿入ソートの実装は上手くいったようです。