CS/알고리즘
정렬 #2) 선택 정렬
alpacadabra
2022. 10. 4. 00:53
선택 정렬은 말그대로 배열에서 최솟값을 선택해 이를 앞으로 이동시키는 행위를 반복하는 것이다.
(내림차순을 원하면 다르게 구현해도 된다. 최댓값을 선택해도 되고, 앞이 아닌 뒤로 이동시켜도 된다.)
위 그림처럼 최솟값을 선택하고, 이를 i번째 위치로 이동시키는 작업을 반복한다.
굉장히 단순하지만 그만큼 시간 복잡도도 상당하다. O(n^2)이다.
왜냐하면, 최솟값을 구하기 위한 비교 작업이 각 회차마다 (n - 1), (n - 2), ... 1번씩 이루어지는데
이를 모두 더하면 n * (n - 1) / 2 가 된다. 따라서 O(n^2)이다.
int[] num = { 6, 3, 4, 1, 5, 7, 2 };
int minIndex;
for (int i = 0; i < num.Length; i++)
{
minIndex = i;
for (int j = i + 1; j < num.Length; j++)
{
if (num[j] < num[minIndex])
minIndex = j;
}
(num[i], num[minIndex]) = (num[minIndex], num[i]); //Swap
}