以前、選択ソートの実装を試してみた事がありました。
-
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パターンある事がわかりました。
ちょっとずつ調べて実装していきたいと思っています。