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 |