選択ソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[Image:Selection sort animation.gif|none|288px|Selection Sort Animation]]
|data=[[配列]]
|time=''О(n²)''
|best-time=''О(n²)''
|average-time=''О(n²)''
|space=''О(n)'' total, ''O(1)'' auxiliary
|optimal=No
}}
'''選択ソート'''（{{lang-en-short|selection sort}}）は、[[ソート]]の[[アルゴリズム]]の一つ。
[[配列]]から[[最小値]]を探し、配列の先頭要素と入れ替えていくことで並べ替える。

[[計算複雑性|最良時間計算量]]は {{math|[[ランダウの記号|O]](''n''<sup>2</sup>)}} と遅いため、一般には[[クイックソート]]などのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。

選択ソートは内部ソートである。また、[[安定ソート]]ではない。

選択ソートの改良として、[[ヒープソート]]が挙げられる。

==アルゴリズム==
[[File:Selection-Sort-Animation.gif|thumb|Selection-Sort-Animation]]
選択ソートは以下の手順で行う：

# 1 番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する（1番目の要素までソート済みとなる）
# 以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する
# すべての要素がソート済みになったら処理を終了する

上記は[[昇順]]への並べ替えだが、[[降順]]の場合も同様に、最小値でなく最大値を検索することで実現できる。

また、各ループ毎に最小値と最大値との両方を探し、両端の要素を同時に確定させる手法もあり、'''{{en|double selection sort}}'''と呼ばれる。

=== 擬似コード ===
<syntaxhighlight lang="text">
for I := 1 to N
  min := I
  for J := I+1 to N  
    if data[J] < data[min] then
      min := J
    end if
  end for
  swap(data[I], data[min])
end for
</syntaxhighlight>

===動作例===
初期データ: 8 4 3 7 6 5 2 1　

太字はソート完了した部分

: '''1''' 4 3 7 6 5 2 8 （1回目のループ終了時）
: '''1 2''' 3 7 6 5 4 8 （2回目のループ終了時）
: '''1 2 3''' 7 6 5 4 8 （3回目のループ終了時）
: '''1 2 3 4''' 6 5 7 8 （4回目のループ終了時）
: '''1 2 3 4 5''' 6 7 8 （5回目のループ終了時）
::この例では、一見して、この時点で既にソート完了したとわかる。しかしデータが多数の場合はそうはいかないし、アルゴリズムで「一見して」ソート完了か否か判断できない。アルゴリズム通りに最後まで処理する必要がある。
: '''1 2 3 4 5 6''' 7 8 （6回目のループ終了時）
: '''1 2 3 4 5 6 7 8''' （7回目のループ終了時）

==計算時間==
以下、ソートする配列の要素数を {{mvar|n}} とする。

要素の比較に関して、各ループで {{math|''n'' &minus; 1}} 回、{{math|''n'' &minus; 2}} 回、……と行われ、処理全体としては <math>\sum_{k=1}^{n - 1} k = \frac{n(n - 1)}{2}</math> 回行われる。

要素の交換に関して、各ループで最大1回行われ、処理全体では多くとも {{math|''n'' &minus; 1}} 回となる。

[[バブルソート]]と比較すると、要素の比較回数は同じだが交換回数が少ないため、選択ソートの方が高速である。

==安定性==
選択ソートは[[安定ソート]]ではなく、複数の同値の要素を持つ配列に対して、同値の要素同士の順序は保存されない。
例えば配列 (2a 2b 1) に対して選択ソートを行うと、

: 2a 2b 1 （初期状態）
: '''1''' 2b 2a （1回目のループ終了時）
: '''1 2b''' 2a （2回目のループ終了時）
: '''1 2b 2a''' （終了状態）

となる（2a, 2b は同値とする）。ソートの前後で 2a, 2bの順序が変更されており、安定でないことが確かめられる。

== 実装 ==

=== Python ===

[[Python]] での実装例を示す。
[[In-placeアルゴリズム|In-place]] 版の実装は以下の通り。
<syntaxhighlight lang="python">
def minIndex(x, i):
    mi = i
    for j in range(i + 1, len(x)):
        if x[j] < x[mi]:
            mi = j
    return mi

def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def inplaceSelectionSort(seq):
    for i in range(len(seq)):
        mi = minIndex(seq, i)
        swap(seq, i, mi)
</syntaxhighlight>

非 in-place 版は上記に配列のコピーを渡すことで実現できるが、例えば以下のように直接実装することもできる。

<syntaxhighlight lang="python">
def nonInplaceSelectionSort(seq):
    ind = [*range(len(seq))]
    res = []    
    for i in range(len(seq)):
        k = 0
        for j in range(len(ind)):
            if seq[ind[j]] < seq[ind[k]]:
                k = j
        res.append(ind.pop(k))
    return [seq[i] for i in res]
</syntaxhighlight>

=== C# ===
[[C Sharp|C#]] での実装は以下の通り。
<syntaxhighlight lang="csharp">
namespace Algorithms
{
class SelectionSort
{
    static void sort(int[] x) {
        for(int i = 0; i < x.Length; i++) {
            int min = i;
            for(int j = i + 1; j < x.Length; j++) {
                if(x[j] < x[min]) {
                    min = j;
                }
            }
            int t = x[i];
            x[i] = x[min];
            x[min] = t;
        }
    }
}
}
</syntaxhighlight>

===Scheme===

[[Scheme]] での実装を以下に示す。

<syntaxhighlight lang="scheme">
(require-extension srfi-1)              ; 実装依存。SRFI-1 と言うライブラリを用いる。

(define (selection-sort ls)
  (let loop ((ls ls) (acc '()))
    (if (null? ls)
        (reverse acc)
        (let ((x (apply min ls)))
          (loop (remove (lambda (y)
                          (= y x)) ls) (cons x acc))))))
</syntaxhighlight>


{{ソート}}
[[Category:ソート|せんたくそおと]]