Unity 개발자를 위한 C# Selection Sort(선택 정렬) 구현

Selection Sort(선택 정렬)는 현재 구간에서 최솟값(또는 최댓값)을 “선택”한 뒤, 그 값을 구간의 시작 위치로 한 번 교환하여 정렬을 진행하는 방식입니다.

 

Bubble Sort가 “인접한 두 값을 비교하며 필요할 때마다 교환(인접 교환)”을 반복한다면, Selection Sort는 “현재 구간 전체를 훑어 최소(또는 최대)를 찾고, 그 결과를 한 번 교환(선택 후 교환)”합니다. 두 알고리즘 모두 비교 기반 정렬이며, 비교 흐름과 교환(스왑) 흐름이 어떻게 구성되는지를 기준으로 보면 구조가 선명해집니다.

 

정렬 비용을 “빠르다/느리다”로 단순화하면, 실제로 비용을 만드는 요소(비교 횟수, 데이터 이동/교환 횟수, 분기 패턴)를 놓치기 쉽습니다. Selection Sort는 특히 비교 횟수는 많지만 교환 횟수는 제한되는 구조이므로, 비교/교환 관점으로 보는 것이 가장 정확합니다.

---

1. Selection Sort의 구조와 동작 방식

1.1 기본 아이디어

정렬되지 않은 구간을 [i .. N-1]라고 할 때, Selection Sort는 매 Pass마다 다음을 수행합니다.

• i 위치에 들어갈 값(최솟값)을 구간 전체에서 찾는다.
• 찾은 최솟값의 인덱스(minIndex)를 i와 교환한다.
• i를 1 증가시키며 정렬된 구간을 확장한다.

1.2 Pass 단위 동작

Pass i는 “i에 들어갈 최솟값을 확정”하는 단계입니다.

• 시작 시점: i부터 끝까지는 정렬되지 않은 구간
• 진행: j = i+1 .. N-1을 순회하며 최솟값 후보를 갱신
• 종료: 최솟값 인덱스가 i가 아니라면 딱 한 번 스왑

한 Pass가 끝나면 i 위치의 값은 최종 위치가 확정됩니다.
즉, “정렬된 prefix가 1칸씩 늘어난다”는 점에서 구조가 명확합니다.

 

※ 동작을 시각적으로 확인해보기

아래 링크는 Selection Sort의 현재 구간 전체를 탐색하여 최솟값(또는 최댓값)을 선택한 뒤, 한 번의 교환으로 위치를 확정하는 과정을 단계별로 시각화해 주는 도구입니다. 각 패스(pass)마다 “선택 → 1회 교환”이 어떻게 이루어지는지 확인할 수 있습니다.

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

---

2. 왜 O(N²)이 되는가 (비교 흐름 기준)

Selection Sort의 핵심 비용은 “최솟값 탐색”입니다. Pass i에서 최솟값을 찾기 위해 비교하는 횟수는 정렬되지 않은 구간 길이에 비례합니다.

• Pass 0: (N-1)번 비교 (0 뒤의 모든 값과 비교)
• Pass 1: (N-2)번 비교
• ...
• Pass N-2: 1번 비교

따라서 총 비교 횟수는 다음 합으로 누적됩니다.

(N - 1) + (N - 2) + ... + 2 + 1
= N(N - 1) / 2

이 누적 비교 구조 때문에 시간 복잡도는 O(N²)로 표현됩니다.

 

Bubble Sort도 평균/최악 관점에서 비교가 누적되어 O(N²)로 분류되는 경우가 많습니다. 다만 두 알고리즘의 차이는 교환(스왑) 횟수에서 더 선명합니다.

• Bubble Sort: 인접 교환이 반복되므로 교환이 매우 자주 발생할 수 있음
• Selection Sort: Pass당 최대 1회 스왑 → 전체 스왑 횟수는 최대 (N-1)

즉, 비교 횟수는 유사한 범위에 있으나, 교환 횟수(데이터 이동) 구조는 서로 다르다는 점이 핵심입니다.

---

3. Selection Sort의 특징과 한계

3.1 교환 횟수가 최대 N-1로 제한됨

Selection Sort는 매 Pass마다 “최솟값을 찾고 마지막에 한 번만 교환”합니다. 따라서 스왑은 최대 (N-1)번입니다.

 

데이터 이동 비용이 큰 타입(큰 구조체, 비용이 큰 복사/이동)에서는 “비교는 많이 하지만 이동은 제한한다”는 특성이 의미를 가질 수 있습니다. (단, C#의 일반적인 int 배열에서는 이동 비용이 매우 작습니다.)

 

3.2 이미 정렬된 경우에도 비교를 줄일 수 없음

Selection Sort는 “최솟값 탐색”을 Pass마다 끝까지 수행합니다. 입력이 이미 정렬되어 있어도, 각 Pass는 구간 전체를 확인해야 “최솟값이 i에 있다”는 사실을 알 수 있습니다.

 

즉, 비교 횟수가 입력 상태에 크게 의존하지 않는 구조입니다. 이 점은 “정렬 여부를 빠르게 감지해 루프를 단축”할 여지가 있는 방식과 대비됩니다.

 

3.3 안정 정렬(Stable Sort)이 아님

Selection Sort는 각 Pass에서 최솟값(또는 최댓값)을 찾은 뒤, 현재 위치 i와 직접 교환(swap)합니다. 이 교환은 “최솟값을 앞에 배치한다”는 목적만 달성하며, 중간에 있던 원소들의 상대 순서는 고려하지 않습니다. 따라서 동일한 키를 가진 원소가 존재할 때, 정렬 결과에서 그 원소들의 상대 순서가 유지된다고 보장할 수 없습니다. 즉, 일반적인 Selection Sort는 안정 정렬(Stable Sort)이 아닙니다.

 

예를 들어 아래 배열에서, 숫자(키)는 같지만 꼬리표(A/B)가 다른 두 원소가 있다고 가정합니다. (A/B는 “원래의 상대 순서”를 구분하기 위한 표기입니다.)

[(2,A), (2,B), (1,C)]

 

Pass 0에서 구간 [0..2]의 최솟값은 (1,C)이며, 인덱스 2에 있습니다. Selection Sort는 이 최솟값을 현재 위치 i = 0과 교환합니다.

swap(0, 2)
[(1,C), (2,B), (2,A)]

 

이 결과에서 확인할 수 있듯이, 정렬 전에는 (2,A)가 (2,B)보다 앞에 있었지만, 정렬 과정의 교환으로 인해 최종 배열에서는 (2,B)가 (2,A)보다 앞에 위치하게 됩니다. 즉, 동일 키(2)를 가진 원소들의 상대 순서가 바뀔 수 있으므로 안정 정렬이 아닙니다.

---

4. 실행 흐름을 예제로 확인하기

예제 배열: [64, 25, 12, 22, 11]
정렬 기준: 오름차순

 

Pass 0 (i = 0)

현재 기준 위치 i=0에 들어갈 최솟값을 구간 [0..4]에서 찾습니다.

• 초기: minIndex = 0 (값 64)
• j=1: 25 < 64 → minIndex = 1
• j=2: 12 < 25 → minIndex = 2
• j=3: 22 < 12 → 변화 없음
• j=4: 11 < 12 → minIndex = 4

Pass 0 종료 시점에 최솟값(11)의 위치는 4이고, i(0)와 다르므로 스왑을 수행합니다.

스왑(0,4) → [11, 25, 12, 22, 64]
0번 인덱스의 값(11)이 최종 위치로 확정됩니다.

 

Pass 1 (i = 1)

구간 [1..4]에서 최솟값을 찾아 1에 배치합니다.

• 초기: minIndex = 1 (값 25)
• j=2: 12 < 25 → minIndex = 2
• j=3: 22 < 12 → 변화 없음
• j=4: 64 < 12 → 변화 없음

스왑(1,2) → [11, 12, 25, 22, 64]
1번 인덱스의 값(12)이 최종 위치로 확정됩니다.

 

Pass 2 (i = 2)

구간 [2..4]에서 최솟값을 찾아 2에 배치합니다.

• 초기: minIndex = 2 (값 25)
• j=3: 22 < 25 → minIndex = 3
• j=4: 64 < 22 → 변화 없음

스왑(2,3) → [11, 12, 22, 25, 64]
2번 인덱스의 값(22)이 최종 위치로 확정됩니다.

 

Pass 3 (i = 3)

구간 [3..4]에서 최솟값을 찾습니다.

• 초기: minIndex = 3 (값 25)
• j=4: 64 < 25 → 변화 없음

minIndex가 i와 같으므로 스왑이 발생하지 않습니다.
배열은 [11, 12, 22, 25, 64] 상태로 유지되며, 정렬이 완료됩니다.

이 예제에서 확인할 수 있는 구조는 다음과 같습니다.

• 각 Pass는 “최솟값 탐색(비교 누적) + 필요 시 단 1회 스왑”으로 구성
• Pass 종료 시점에 i 위치가 확정되며, 정렬된 구간이 한 칸씩 증가

---

5. C# 기반 Selection Sort 직접 구현 코드

아래 코드는 int[]에 대한 기본 Selection Sort 구현입니다.
가독성을 우선하며, 불필요한 트릭(비트 스왑, LINQ, 복잡한 최적화)은 포함하지 않습니다.

using System;

namespace Daebak.Common.Algorithms.Sorting
{
    public static class SelectionSort
    {
        public static void Sort(int[] array)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            int n = array.Length;
            if (n <= 1)
            {
                return;
            }

            for (int i = 0; i < n - 1; i++)
            {
                int minIndex = i;

                for (int j = i + 1; j < n; j++)
                {
                    if (array[j] < array[minIndex])
                    {
                        minIndex = j;
                    }
                }

                if (minIndex != i)
                {
                    Swap(array, i, minIndex);
                }
            }
        }

        private static void Swap(int[] array, int a, int b)
        {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
        }
    }
}

구조적으로 중요한 포인트는 다음 두 가지입니다.

• 내부 루프(j)는 “최솟값 탐색”만 수행하며, 탐색 중에는 교환하지 않습니다.
• 스왑은 Pass 종료 시점에 조건적으로 1회 수행됩니다(minIndex != i).

---

6. Unity 환경에서 테스트 해보기

using UnityEngine;
using Daebak.Common.Algorithms.Sorting;

public class Test_SelectionSort : MonoBehaviour
{
    private void Start()
    {
        int[] data = new int[] { 64, 25, 12, 22, 11 };

        Debug.Log("Before Sort : " + string.Join(", ", data));

        SelectionSort.Sort(data);

        Debug.Log("After Sort : " + string.Join(", ", data));
    }
}

이 테스트는 다음을 확인하기에 충분합니다.

• 정렬 전/후 배열 상태가 명확히 출력되는지
• 정렬 로직이 Unity 환경과 분리되어 재사용 가능한지

출력 결과

Before Sort : 64, 25, 12, 22, 11
After Sort : 11, 12, 22, 25, 64

---

7. 마무리

Selection Sort는 “구간에서 최솟값을 선택하고, Pass당 최대 1회 교환”이라는 구조가 명확한 정렬입니다. 따라서 비교/교환 관점에서 비용을 분해해 이해하기에 좋은 기준점이 됩니다.

• 비교: (N-1) + (N-2) + ... + 1 형태로 누적되어 O(N²)
• 교환: Pass당 최대 1회 → 전체 최대 (N-1)회

Bubble Sort가 “인접 비교/인접 교환”을 반복해 정렬이 진행되는 구조라면, Selection Sort는 “선택(탐색) 후 교환”으로 정렬된 구간을 확장하는 구조입니다. 이 차이를 비교/교환 관점으로 정리해두면, Insertion Sort처럼 “이동이 많은 대신 비교 흐름이 달라지는 방식”이나, Quick Sort처럼 “분할을 통해 비교 구조 자체가 달라지는 방식”을 해석할 때도 기준이 흔들리지 않습니다.

 

※ 다음 글에서는 Insertion Sort를 살펴보며, 이미 정렬된 구간에 새로운 요소를 삽입하는 방식이 데이터 이동(shift)과 입력 상태에 따른 성능 차이를 어떻게 만들어내는지를 중심으로 정리합니다.