정렬 알고리즘의 기초 2편 : 선택 정렬 (Selection Sort)

정렬 알고리즘의 두 번째 주제로 소개할 방식은 선택 정렬입니다.
버블 정렬과 마찬가지로 단순한 구조를 가지고 있어, 알고리즘 학습 입문자에게 적합한 방식입니다.

이번 글에서는 선택 정렬의 작동 원리와 구현 코드, 그리고 이 정렬에 ‘선택’이라는 이름이 붙은 이유를 함께 살펴보겠습니다.

 

선택 정렬이란?

선택 정렬은 아직 정렬되지 않은 부분 중에서 가장 작은 값을 선택하여, 그 값을 앞쪽으로 이동시키는 방식입니다.
즉, i번째 자리에 들어갈 값을 배열의 나머지 구간에서 '선택' 해서 자리를 바꾸는 것이 특징입니다.

이 과정을 전체 길이만큼 반복하면 오름차순 정렬이 완성됩니다.

 

 

작동 방식 요약

1. 현재 위치(i)를 기준으로, 그 뒤에 있는 값들 중 가장 작은 값을 찾습니다.

2. 그 값의 위치(minIndex)를 기억해둡니다.

3. 가장 작은 값과 i번째 값을 교환합니다.

4. 다음 위치로 이동하여 위 과정을 반복합니다.

 

C# 코드 예시

int[] numbers = { 52, 86, 3, 79, 45, 12, 99, 23, 56, 78 };

for (int i = 0; i < numbers.Length; i++)
{
    int minIndex = i;

    for (int j = i + 1; j < numbers.Length; j++)
    {
        if (numbers[j] < numbers[minIndex])
        {
            minIndex = j;
        }
    }

    // 튜플을 이용한 값 교환
    (numbers[i], numbers[minIndex]) = (numbers[minIndex], numbers[i]);
}

Console.WriteLine(string.Join(", ", numbers));

 

위 코드에서는 minIndex라는 변수를 이용하여 아직 정렬되지 않은 부분 중 가장 작은 값을 찾아내고, 해당 값과 현재 위치(i)의 값을 교환하는 구조로 구성되어 있습니다.

 

선택 정렬이라는 이름의 유래

선택 정렬은 각 단계마다 "정렬되지 않은 구간에서 가장 작은 값을 선택"하여 지정된 위치로 보내는 방식입니다.
즉, '선택해서 정렬한다' 는 점에서 Selection Sort(선택 정렬) 이라는 이름이 붙었습니다.

 

마무리

선택 정렬은 단순하고 구현이 쉬운 알고리즘이지만, 버블 정렬과 마찬가지로 시간 복잡도가 O(n²)로 비교적 느린 편입니다. 그럼에도 불구하고 정렬 알고리즘의 구조를 이해하는 데 매우 유용한 학습 자료입니다.

다음 글에서는 삽입 정렬(Insertion Sort) 을 다룰 예정입니다.

정렬된 구간에 값을 '끼워 넣는' 방식이 어떻게 작동하는지 살펴보겠습니다.