選択ソートについて

考え方


「ソート済み」と「未ソート」の2つのステップに分けられる。

未ソート部の中で最も小さい要素を特定して未ソート部の最も小さいインデックスと交換する。これを繰り返す。

計算量について


$Sn = (n - 1) + (n - 2) + (n - 3) … + 2 + 1$

となる。これは等差数列なので

$\displaystyle \sum_{ i = 1 }^{ n } i = \frac{ n^2 - n }{ 2 } $

となり $O(n^2)$ となる。

実装


例えば5, 6, 4, 2, 1, 3という配列があり、これを選択ソートでソートするには下記のような感じになる。

3つの変数を用いる。ここでは仮にijminjとする。

  • i: 全体の配列を走査するループ変数。ループ中は未ソート部の先頭と同じになる
  • j: 未ソート部の配列を先頭から末尾に向かって走査するループ変数
  • minj: 未ソート部で最も小さい値のインデックスを格納する変数

変数iとjを用いた2重ループになる。

  1. 配列の要素数を取得する
  2. minj変数に未ソート部の初めのインデックスを格納する
  3. jを用いたループで未ソート部の配列を走査する
    • このときjの初期値はminjになる
    • minjの値よりjの値が小さい場合はminjjをセットする
    • jが未ソート部の全てを走査し終えるとiminjをセットする
  4. あとはiが配列の最後にたどり着くまで2~3を繰り返す

C#での実装


前例をC#で実装するとこうなる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
using System;
using System.Linq;
class Program
{
static void Main()
{
var nums = new int[] { 5, 6, 4, 2, 1, 3 };
var n = nums.length;
var minj = 0;
for (var i = 0; i < n; i++)
{
minj = i;
for (var j = minj; j < n; j++)
{
if (nums[j] < nums[minj])
{
minj = j;
}
}
var tmp = nums[i];
nums[i] = nums[minj];
nums[minj] = tmp;
}
foreach (var x in nums)
{
Console.Write("{0} ", x);
};
}
}

おわり。

参考


AOJ SelectionSort