Sorting Algorithm-Simple Selection Sort

Simple Selection Sort-単純選択ソート
Algorithm:
n−i次キーワード間の比較により、n−i+1個のレコードの中からキーワードが最も小さいレコードが選択され、i番目(1<=i<=n)個のレコードと交換される.
Ex:
4,3,1,2初回,最小要素は1,1,4交換
1,3,4,2 1不動,2回目,最小要素は2,2,3交換
1,2,4,3 1,2不動,3回目,最小要素3,3,4交換
1,2,3,4
Code:

void Selection_Sort(vector<int> &v)
{
	for (int i = 0; i < v.size()-1; i++)
	{
		int min = i;
		for (int j = i + 1;j<v.size(); j++)   //       
		{
			if (v[min]> v[j])
				min = j;
		}
		int temp = v[min];
		v[min] = v[i];
		v[i] = temp;
	}
}

Analysis:
ソートを簡単に選択する過程から見ると、移動データを交換する回数がかなり少ないことが最大の特徴であり、時間を節約することができます.その時間的複雑さを解析すると,最良最悪の場合にかかわらず比較回数は同じであり,i番目のソートではn−i次キーワードの比較が必要であり,この場合はn(n−1)/2回の比較が必要であることが分かった.一方,交換回数については,最良の場合,交換が0回,最悪の場合,逆シーケンスの場合,n−1回を交換し,最終的なソート時間に基づいて比較と交換の回数の総和であるため,総時間複雑度は依然としてO(n^2)である.
バブルソートと同様にO(n^2)であるにもかかわらず,単純にソートを選択する性能はバブルソートよりやや優れていると言える.
unstable sort