はじめに

　大学の授業で選択ソートについて習ったので、自分自身の理解を深める目的で、最低限の情報だけ記事にまとめてみました。

操作

　最小値を探して先頭と入れ替え、先頭を除いた部分でまた最小値を探し、その部分の先頭とまた入れ替える...というのを繰り返してソートを行います。

データ数を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)のため遅い
ほぼソート済みでも効率が改善されない
安定ソートではない

→　交換をあまり行いたくない場合や、初心者向けのソートとして適正あり

最後に

　ここまで読んで下さりありがとうございました。正直、筆者はソートなどのアルゴリズム系が、あまり得意ではないです。しかし、基本情報技術者試験などでも問われる内容ですし、毎週授業で１つずつ扱うみたいなので、復習+α的な感じで記事にしていきたいと思っています。