#6 ソートアルゴリズム 選択ソート
アルゴリズムといえばソート！(別にそういうわけではありません。)
アルゴリズムの題材としてはソートは良い題材です。
同じ並び替えですが、様々な方法があり、それぞれ特徴があります。
今回はソートの中でも基本的な選択ソートを説明します。
選択ソート
配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。
最良時間計算量は O(n2) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。
並べ替えのアルゴリズムの中でへ最も基本的です。
シンプルに小さいのから順に並べましょうといったもの。
特徴としては、計算量のオーダーが$$N^2$$と処理時間か指数関数的に増えていくのでソートするデータ量が少ない時に使います。
また、配列の中でソートするだけですのでメモリ消費は少ないソートです。
メモリの使用量に限りがある場合などでも使います。
コード
def select_sort(lists):
print('元データ:',lists)
cnt=0
for i in range(0,len(lists)-1):
m=i
for j in range(i+1,len(lists)):
if lists[j] < lists[m]:
m=j
lists[i],lists[m] = lists[m],lists[i]
cnt+=1
print(lists,i+1)
print('ソート後',lists)
print('入れ替え回数:',cnt)
def gen_val(n):
return [r.randint(0,1000) for i in range(0,n)]
if __name__ == "__main__":
a=gen_val(10)
start=t.time()
select_sort(a)
print(t.time()-start)結果
コードの処理結果を見ると小さい順に並んでいく過程がわかります。
元データ: [329, 624, 366, 266, 614, 328, 679, 43, 38, 680]
[38, 624, 366, 266, 614, 328, 679, 43, 329, 680] 1
[38, 43, 366, 266, 614, 328, 679, 624, 329, 680] 2
[38, 43, 266, 366, 614, 328, 679, 624, 329, 680] 3
[38, 43, 266, 328, 614, 366, 679, 624, 329, 680] 4
[38, 43, 266, 328, 329, 366, 679, 624, 614, 680] 5
[38, 43, 266, 328, 329, 366, 679, 624, 614, 680] 6
[38, 43, 266, 328, 329, 366, 614, 624, 679, 680] 7
[38, 43, 266, 328, 329, 366, 614, 624, 679, 680] 8
[38, 43, 266, 328, 329, 366, 614, 624, 679, 680] 9
ソート後 [38, 43, 266, 328, 329, 366, 614, 624, 679, 680]
入れ替え回数: 9
処理時間:0.031036853790283203
参考書籍
いいなと思ったら応援しよう！
