Algorithm

Selection Sort

HYuk 2022. 6. 27. 18:17
728x90

선택정렬

가장 작은 것을 선택해서 제일 앞으로 보내는 것이다.

 

따라서

 5 3 4 1 2 라고 있으면

1 5 3 4 2

1 2 5 3 4

1 2 3 5 4

1 2 3 4 5

위와 같은 형태로 정렬된다.

 

void SelectionSort(vector<int>& _vec)
{
	int iMin = 0, iIdx = 0;
	for (int i = 0; i < _vec.size(); ++i)
	{
		bool bCheck = true;
		for (int j = i; j < _vec.size(); ++j)
		{
			if (bCheck) // 처음에 한번 저장
			{
				iMin = _vec[j];
				iIdx = j;
				bCheck = !bCheck;
				continue;
			}
			if (iMin > _vec[j]) // 더 작은 값을 발견하면 해당 인덱스와 값을 저장해둠
			{
				iMin = _vec[j];
				iIdx = j;
			}
		}
		// 그 작은 값을 맨 앞으로 이동
		int iTemp = _vec[i];
		_vec[i] = iMin;
		_vec[iIdx] = iTemp;
	}
}

 

연산은 N의 등차수열의 합만큼 필요하다

N(N+1)/2 만큼 필요하다.

따라서 시간복잡도는 O(N^2)을 가진다.

 

하지만 실제로 버블정렬보다 빠른 이유는 매번 비교하여 자리를 바꿔주는 버블정렬과는 달리

제일 작은 값만 앞으로 보내주기 때문에 실제로 버블정렬보다는 빠르다.

728x90

'Algorithm' 카테고리의 다른 글

전체 탐색에서 부분합 문제를 비트를 사용하는 방법  (0) 2023.04.09
Bubble Sort  (1) 2022.06.27