정렬 #2) 선택 정렬

선택 정렬은 말그대로 배열에서 최솟값을 선택해 이를 앞으로 이동시키는 행위를 반복하는 것이다.

(내림차순을 원하면 다르게 구현해도 된다. 최댓값을 선택해도 되고, 앞이 아닌 뒤로 이동시켜도 된다.)

 

---

---

 

위 그림처럼 최솟값을 선택하고, 이를 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
}

 

정렬 결과