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)

実行結果

あい

今回は
選択ソートを
pythonを利用して
実装していきます

昇順選択ソート処理手順

1.最も小さい値を探し先頭と入れ替える

2.先頭と探索範囲を1つシフトして

最も小さい値を探索

6と4を入れ替える

これを延々と繰り返し昇順にソート完了です

選択ソート実装

昇順に並び替える選択ソートの

処理を実装します

data = [8,6,5,3,6,10,4]
len = len(data)

for i in range(len):
    m = i
    for j in range(i+1,len):
         if data[j] < data[m]:
             m = j
    data[i],data[m] = data[m], data[i]
print(data, "ソート後のデータ")

実行結果

アルゴを解析していきます

1.データを格納する

data = [8,6,5,3,6,10,4]
len = len(data)

上記コードを読むと

データはリストに格納されています

リストにはインデックスが紐づいているので

d[i]とコードに書くと

対応するインデックスから

要素を取得することが可能です

2.繰り返し処理の最初に最小値が存在する

インデックスを保存する変数mを作ります

for i in range(len):
    m = i

コードを読むと

初期値にm = 0が入ることが分かります

2.最小値を探索する

for i in range(len):
    m = i
    for j in range(i+1,len):
         if data[j] < data[m]:
             m = j

3.最小値と0番地を入れ替える

    data[i],data[m] = data[m], data[i]

4.再び処理が繰り返しの最初に戻ります

for i in range(len):
    m = i

m = 1が入ります

5.最小値を1番地以降から探し

最小値のインデックスを取得します

for i in range(len):
    m = i
    for j in range(i+1,len):
         if data[j] < data[m]:
             m = j

6.最小値と1番地を入れ替える

    data[i],data[m] = data[m], data[i]

これを最後まで繰り返すと

あい

for文(繰り返し処理)を

うまく使ってデータの
探索と交換をやっているんだね!

参考文献

あい

Chapter 5
Lesson 5-1
選択ソートより