【アルゴリズム】Pythonで挿入ソートを実装しアルゴリズムを理解する

あい

今回はpythonで
挿入ソートを
実装しアルゴリズム
を理解します

[R]※本サイトにはプロモーションが含まれています

1 ソートとは
2 挿入ソート処理手順
3 挿入ソート実装
4 参考文献

ソートとは

データを一定の規則に従って並び替える処理

データの並び変え処理には主に

昇順, 降順がある

昇順 : 小さな数から大きな数へ

降順 :大きな数から小さな数へ

以下データを並び替える

昇順にすると

降順にすると

# 初期データ
data = [8, 6, 5, 3, 6, 10, 4]

# 昇順に並べ替え
ascending_data = sorted(data)
print("昇順:", ascending_data)

# 降順に並べ替え
descending_data = sorted(data, reverse=True)
print("降順:", descending_data)

実行結果

挿入ソート処理手順

1.左端と1つ右の値を比較する

2.右の方が小さければ左の値を右にずらし

ずらされた所にあった値はその前に挿入する

3.更に右の値5を6,8と比較し

6,8より小さいので6,8をずらし前に5を挿入する

この処理を繰り返し右端まで

完了した時ソートが完了します

挿入ソート実装

データを昇順にソートするアルゴリズムを

pythonを利用して実装します

data = [8,6,5,3,6,10,4]
n = len(data) 
print(f"データ数 = {n}")

for i in range(0,n):
    tmp = data[i]
    j = i

    while j > 0 and data[j -1] >tmp:
        data[j] = data[j-1]
        j = j - 1
        data[j] = tmp

print(f"ソート後のデータは{data}")

実行結果

処理を説明します

1.データとデータの要素数を変数に格納

data = [8,6,5,3,6,10,4]
n = len(data) 
print(f"データ数 = {n}")

2. j = 0, temp = 8が入る

for i in range(0,n):
    tmp = data[i]
    j = i

3. j = 0より

j > 0を満たしていないので

while内の処理は行われない

    while j > 0 and data[j -1] >tmp:
        data[j] = data[j-1]
        j = j - 1
        data[j] = tmp

4.j = 1, tmp = 6が入る

for i in range(0,n):
    tmp = data[i]
    j = i

5. j = 1, temp = 6より

j > 0 and data[j -1] >tmp

を満たすためwhileの処理に入る

６があった場所に8が挿入され

8があった場所に6が挿入される

    while j > 0 and data[j -1] >tmp:
        data[j] = data[j-1]
        j = j - 1
        data[j] = tmp

7.j =0よりwhileの条件式を抜け

j = 2, temp = 5が入る

8.j = 2, temp = 5より

j > 0 and data[j -1] >tmp

を満たすためwhileの処理に入る

5があった場所に8が挿入され

8があった場所に5が挿入される

    while j > 0 and data[j -1] >tmp:
        data[j] = data[j-1]
        j = j - 1
        data[j] = tmp

9.j = 1, temp = 5より

whileの条件式を満たすので

whileの処理に入る

5があった場所に6が挿入され

6があった場所に5が挿入される

    while j > 0 and data[j -1] >tmp:
        data[j] = data[j-1]
        j = j - 1
        data[j] = tmp

10.j =0よりwhileの条件式を抜け

j = 3, temp = 3が入る

同じ処理を繰り返し右端に来たら

ソート完です

あい

forとwhileで
処理を何回も
繰り返して

いるんだね

参考文献

あい

Chapter 5
Lesson 5-3
挿入ソートより