Python アルゴリズム プログラミング メモ

アルゴリズムの練習 挿入ソート Python

アルゴリズムの練習です。

挿入ソートの実装を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

 

完全一致している事が確認できました。

挿入ソートの実装は上手くいったようです。

 

 

 

 

-Python, アルゴリズム, プログラミング, メモ

Copyright© donguri_pyのblog , 2024 All Rights Reserved.