선택 정렬(Selection Sort) 쉽게 이해하기: 가장 작은 값부터 차곡차곡

알고리즘을 처음 배울 때 가장 먼저 떠올릴 수 있는 가장 원초적이고 직관적인 정렬 방법이 있습니다. 100명의 학생을 키 순서대로 세운다고 할 때, 운동장을 쭉 둘러보며 '가장 키가 작은 학생'을 찾아 맨 앞자리에 세우고, 그다음으로 작은 학생을 찾아 두 번째 자리에 세우는 과정을 끝까지 반복하는 것입니다. 인간의 사고방식과 가장 맞닿아 있는 이 무식하지만 확실한 방법, 바로 '선택 정렬(Selection Sort)'입니다. 비록 실무에서 쓰기에는 속도가 느리지만, 모든 정렬 알고리즘의 뼈대가 되는 위치 교환(Swap)의 개념을 완벽하게 이해할 수 있는 훌륭한 교보재입니다.

1. 최솟값을 향한 끝없는 탐색

선택 정렬의 핵심 로직은 이름 그대로 '선택(Selection)'에 있습니다. 배열이 주어지면, 알고리즘은 현재 정렬되지 않은 구간에서 무조건 최솟값(Minimum)을 찾아냅니다.

1-1. 동작 시뮬레이션

배열 [8, 3, 5, 1, 9]가 있다고 가정해 봅시다.

1. 1라운드: 전체 배열 [8, 3, 5, 1, 9] 중 가장 작은 숫자는 1입니다. 이 1을 맨 앞의 8과 자리를 바꿉니다(Swap). → [1, 3, 5, 8, 9] (1은 정렬 완료)
2. 2라운드: 1을 제외한 나머지 [3, 5, 8, 9] 중 가장 작은 숫자는 3입니다. 마침 두 번째 자리에 있으니 그대로 둡니다. → [1, 3, 5, 8, 9] (1, 3 정렬 완료)
3. 3라운드: 나머지 [5, 8, 9] 중 가장 작은 숫자는 5입니다. 역시 제자리입니다.
4. 이 과정을 배열의 끝에 도달할 때까지 반복합니다.

2. 선택 정렬의 치명적인 한계: O(N^2)의 늪

선택 정렬은 구현이 매우 쉽고, 메모리도 추가로 필요하지 않으며(In-place), 자리를 바꾸는 Swap 연산이 최대 N번밖에 일어나지 않는다는 장점이 있습니다. 하지만 치명적인 단점이 존재합니다. 바로 "배열이 이미 정렬되어 있든 말든, 무조건 끝까지 훑어서 최솟값을 확인해야 한다"는 융통성 없는 고집입니다.

데이터가 10만 개라면, 첫 번째 최솟값을 찾기 위해 10만 번을 훑고, 두 번째를 찾기 위해 9만 9천 번을 훑어야 합니다. 결국 수학적으로 $\frac{N(N-1)}{2}$번의 비교 연산이 발생하며, 데이터의 초기 상태와 무관하게 항상 O(N^2)이라는 끔찍한 시간 복잡도를 기록하게 됩니다. 따라서 코딩 테스트나 실무에서는 절대 메인 정렬로 사용되지 않습니다.

[핵심 요약]
1. 선택 정렬(Selection Sort)은 정렬되지 않은 구간에서 최솟값을 '선택'하여 맨 앞의 데이터와 교환하는 직관적인 정렬 방식입니다.
2. 배열의 상태와 상관없이 매번 나머지 모든 원소를 비교해야 하므로 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(N^2)으로 동일하게 느립니다.
3. 데이터의 비교 횟수는 많지만, 실제로 자리를 바꾸는(Swap) 횟수는 N번 이하로 매우 적다는 독특한 특징이 있습니다.