[정렬 알고리즘, C#] 선택 정렬(Selection Sort)

■ 선택 정렬(Selection Sort)

선택 정렬은 배열에서 값을 하나 선택한 뒤, 뒤쪽 값들과 비교해 최솟값(오름차순 기준)을 찾아 교환하는 방식으로 앞쪽부터 순차적으로 정렬해 나가는 알고리즘이다.

[선택 정렬 예시]

선택 정렬의 동작 방식은 아래와 같다.

1. 배열의 첫 번째 값을 선택한다.
2. 나머지 값들과 비교하면서 가장 작은 값을 찾는다.
3. 찾은 최소값을 현재 위치와 교환한다.
4. 다음 위치로 이동해 배열의 끝까지 이를 반복하며 정렬한다.

즉, 버블 정렬(Bubble Sort)과 달리, 선택 정렬은 각 사이클마다 배열의 길이에 비례한 비교 연산을 수행하지만, 실제로 값의 교환은 한 번만 발생한다.

• 버블 정렬은 인접한 두 값을 비교하며 여러 변 교환을 수행하지만, 선택 정렬은 가장 작은 값을 찾고 한 번만 교환하기 때문.

 

■ 선택 정렬 구현(C#)

public static class SortArray<T> where T : IComparable<T>
{
    // 선택 정렬
    public static void SelectionSort(T[] arr)
    {
        for(var i = 0; i < arr.Length; ++i)
        {
            var minIndex = i;

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

            if(minIndex != i)
            {
                (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
            }
        }
    }
}

선택 정렬의 구현은 매우 간단하다.

현재 위치 값을 기준으로, 그 뒤의 모든 값들과 비교하여 최솟값의 위치를 찾은 뒤, 반복이 끝난 시점에 해당 위치의 값과 교환한다.

• 이때, C#의 튜플 스왑 문법을 활용하면 별도의 임시 변수를 만들지 않고도 간결하게 값을 교환할 수 있다.

 

선택 정렬이 유리한 경우

선택 정렬은 비교 연산은 많이 수행하지만, 교환 횟수는 한 사이클당 최대 1회로 제한되기 때문에 데이터 이동 비용이 중요한 경우에 상대적으로 유리한 정렬 방식이다.

 

▶ 선택 정렬의 시간복잡도

선택 정렬은 이중 반복문을 사용하여 모든 원소를 비교하면서 정렬을 수행하기 때문에, $O(n^2)$의 시간복잡도를 가진다.

• 각 반복 회차마자 최솟값을 찾기 위해 남은 원소들과 비교.
• $\frac{n(n-1)}{2}$번의 비교 연산이 이루어진다.

따라서 입력 데이터의 정렬 상태와 관계없이 항상 일정한 연산량이 발생한다는 특징을 갖는다.