以前、選択ソートの実装を試してみた事がありました。
-
-
Pythonで選択ソートの実装
Pythonで選択ソートを実装してみました。 通常の処理であれば、sort or sorted で処理すれば一瞬なのですが、今回はアルゴリズムの学習の為、あえて選択ソートをループで処理してみました。 ...
続きを見る
結果的にソートは上手く機能していたのですが、よく調べてみると私の実装方法は選択ソートではなくバブルソートに近い実装であるという誤りに気がついたからです。
選択ソートの概念を再度、確認
① 配列の最小値を探す ② 最小値を配列の先頭に移動する ③ ①～②の処理で先頭はソート完了と考えて①～②を繰り返す
今回、上記の概念を再確認した上で実装しなおしてみました。
l = [6, 5, 4, 3, 1, 2,]
"""
選択ソートの実装
① 配列の最小値を探す
② 最小値を配列の先頭に移動する
③ ①～②の処理で先頭はソート完了と考えて①～②を繰り返す
"""
counts = 0
for i in range(len(l)):
min_l = l[i]
for j in range(i, len(l)):
if min_l > l[j]:
min_l = l[j]
for i in range(len(l)):
if l[i] == min_l:
l.pop(i)
l.insert(counts, min_l)
counts += 1
print(l)
まず、最小値を探索していって、「最小値＝先頭に位置する」という考え方が前提になっています。
これは昇順の例で降順は、「最大値＝先頭に位置する」という事で同じように選択ソートが実装できます。
sort 関数でやれば一瞬で解決する、どーって事ない話なのですが、ソートの概念を1つ1つ探ってみると、とても面白い仕組みになっている事が理解できます。
現時点で私が調べた限りですがソートアルゴリズムだけで少なくとも13パターンある事がわかりました。
ちょっとずつ調べて実装していきたいと思っています。