はじめに
大学の授業で選択ソートについて習ったので、自分自身の理解を深める目的で、最低限の情報だけ記事にまとめてみました。
操作
最小値を探して先頭と入れ替え、先頭を除いた部分でまた最小値を探し、その部分の先頭とまた入れ替える...というのを繰り返してソートを行います。
データ数をnとすると、要素は0番目からn-1番目まであります。
１段階目
0番目を最小値に
n-1番目まで見て行って、小さいものがあれば最小値を更新
0番目と最小値を入れ替え
２段階目
1番目を最小値に
同様にn-1番目まで見て行って、小さいものがあれば最小値を更新
1番目と最小値を入れ替え
・
・
・
n-1段階目
n-2番目とn-1番目を比較して小さいほうを最小値に
n-2番目と最小値を入れ替え
可視化
一応記事なので文字で書きましたが、やはり文字で見てもよくわからないので可視化してみました。
計算量
1段階目の比較回数は最初の0番目と1～n-1番目を比較するためn-1回。それ以降は１段階ごとに１回ずつ比較回数は減っていき、最後のn-1段階目で1回になるので、1～n-1までの和が、全体としての比較回数になります。
$$ 比較回数=(𝑛−1)+(𝑛−2)+⋯+1 = \frac{(𝑛−1)((𝑛−1)+1)}{2} = \frac{𝑛^2−n}{2} $$
ということで、データ数をnとしたときの計算量はO(n^2)です。
ソート前の順番によらず、常にこの計算量になります。
安定ソートではない
例えば[7, 2, 3, 7, 5, 1]という配列の場合以下のようになります。（わかりやすくするため７に番号を振っています）
[7-1, 2, 3, 7-2, 5, 1](ソート前)
[1, 2, 3, 7-2, 5, 7-1](1と7を入れ替え)
[1, 2, 3, 5, 7-2, 7-1](5と7を入れ替え)
ソート前と後で7-1と7-2の順番が入れ替わってしまっているので、安定ソートではないことがわかります。
内部ソート
選択ソートは、リスト内の最小値を見つけて順番に入れ替えていくソート方法ですが、後述のコードを見ればわかる通り、入れ替えなどの操作が配列自身のメモリ領域内で完結できるので、内部ソートです。
コード
pythonで書くと、こんな感じになります。
def selection_sort(arr):
for i in range(len(arr)-1):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
総評
強み
- シンプルで実装が簡単
- 入れ替えの回数自体は少なめ（最大n-1）
弱み
- 計算量がO(n^2)のため遅い
- ほぼソート済みでも効率が改善されない
- 安定ソートではない
→ 交換をあまり行いたくない場合や、初心者向けのソートとして適正あり
最後に
ここまで読んで下さりありがとうございました。正直、筆者はソートなどのアルゴリズム系が、あまり得意ではないです。しかし、基本情報技術者試験などでも問われる内容ですし、毎週授業で１つずつ扱うみたいなので、復習+α的な感じで記事にしていきたいと思っています。