選択ソート実装・詳しい計算量解説

選択ソート(Selection Sort)

このサイトでの選択ソートの定義は以下の通りです。¹

計算量 $O(N^2)$

選択ソートのアルゴリズム

選択ソートは未ソート部分から最小値を選択し、未ソート部分の先頭と交換することでソートを行うアルゴリズムです。

詳しく手順を説明すると以下の通りです。

1. 未ソート部分の最小値を選択する
2. 未ソート部分の先頭と最小値を交換する
3. 未ソート部分を狭める
4. 未ソート部分がなくなるまで繰り返す

以下に C 言語での実装例を示します。

void selectionSort(int *data, int n)
{
	int i, j;
	int low;
	for (i = 0; i < n; i++)
	{
		low = i;
		for (j = i; j < n; j++)
		{
			if (data[low] < data[j])
			{
				low = j;
			}
		}
		int tmp;
		tmp = data[low];
		data[low] = data[i];
		data[i] = tmp;
	}
}

選択ソートの計算量

今回は選択ソートのデータ比較回数について着目し、計算量の議論を行います。

選択ソートのデータ比較回数は、未ソート部分の最小値を選択するため、未ソート部分の数になります。

よって、データを選択するごとに、$N-1, N-2,　N-3, \cdots, 1$回のデータ比較が必要になります。

この場合、データ比較回数は以下のようになります。

よって、選択ソートの計算量は $O(N^2)$ となります。