#Pythonで学ぶアルゴリズム< 選択ソート >
##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第15弾として選択ソートを扱う．今回からしばらく並べ替えについてのアルゴリズムを学ぶ．
##なぜソートのアルゴリズムを学ぶのか？
・ライブラリの利用が一般的だが，その実装を知ることは大切
・ソートの考え方はほかのプログラムを作るにあたって参考になる部分が多い
・ループや条件分岐，リストの扱い，関数の作成，再帰呼び出しといったプログラミングの基本を学べるだけでなく，計算量の比較やその必要性を示す理想的な問題
・それぞれの処理はシンプルで，実装にそれほど時間がかかるわけでもなく，実用的なプログラムである
##選択ソート
リストの中で最小値を探し，その最小値と先頭の場所を入れ替える．続いて，2番目を基準として，先頭を除いた最小値を探しまた入れ替える．これを繰り返すことで，昇順(小さいもの順)に並べ替えることができる．そのイメージ図を次に示す．
上図のように，最小値と入れ替える基準を変えていくことで，昇順に並べ替えができることが分かる．
##実装
先ほどの手順に従ったプログラムのコードとそのときの出力を以下に示す．
#####コード
"""
2021/01/07
@Yuya Shimizu
選択ソート
"""
def select_sort(data):
"""選択ソート：自分よりも小さな値と場所を入れ替えて，昇順に並べ替える"""
for i in range(len(data)):
Min = i #入れ替え対象をセット
for j in range(i+1, len(data)):
#セットした値よりも小さな値があれば，その位置を最小値として記録
if data[j] < data[Min]:
Min = j
#いまの位置と最小値を入れ替え ⇒ 結果，左から小さい順に並ぶ
data[i], data[Min] = data[Min], data[i]
return data #並べ替えを終えたデータを返す
if __name__ == '__main__':
DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
sort = select_sort(DATA.copy()) #後に比較するため，リストが変更されないようにcopyしたものを引数にする
print(f"{DATA} → {sort}")
#####出力
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
ちゃんと昇順に並べ替えられていることが分かる．
今回は並べ替える前後での比較をしたいがために，あえてsortという変数に結果を格納し，さらに関数への引数はDATA.copy()というようにcopy関数により，引数に影響が出ないようにしている．並べ替えるだけなら，そのような操作は必要でなく，select_sort(DATA)とすればよい．
##選択ソートの計算量
最後に計算量について触れる．
1つ目の最小値を探すには残りの$n-1$個の要素との比較が必要で，同様に2つ目，3つ目では，$n-2$回，$n-3$回の比較が必要になる．したがって，全体での比較回数は$(n-1) + (n-2) + ... + 1 = \frac{n(n-1)}{2}$となる．$\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$となるが，$n$が大きくなると第1項に対して第2項は十分小さく無視できるため，**計算量はオーダー記法で表すと，$O(n^2)$**となる．
##感想
特に難しいことはなく，今までの復習も併せてできそうだと感じた．今回は並べ替え1つ目選択ソートということで他との比較はできないが，これから学ぶほかの並べ替えアルゴリズムが楽しみであり，士気が高められる．また，オーダー記法についても慣れてきた気がする．
##参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社