선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 정렬된 영역의 맨 뒤로 보내는 알고리즘이다. 매 단계마다 최솟값을 선택(Selection)한다고 해서 선택 정렬이라는 이름이 붙었다. 구현이 직관적이지만 성능은 O(n²)으로 비효율적이다
핵심 원리
선택 정렬은 다음 과정을 반복한다
- 정렬되지 않은 영역에서 최솟값을 찾는다
- 최솟값을 정렬되지 않은 영역의 첫 번째 원소와 교환한다
- 정렬된 영역을 한 칸 확장한다
동작 과정 상세 분석
배열 [4, 2, 3, 1]을 오름차순으로 정렬하는 과정을 단계별로 살펴본다
[4, 2, 1, 3]
↑________↑
정렬되지 않은 영역 (전체)
1단계: 첫 번째 최솟값 찾기
[4, 2, 1, 3] ← 현재 최솟값: 4
4와 2 비교 → 2가 더 작음
현재 최솟값: 2
2와 1 비교 → 1이 더 작음
현재 최솟값: 1
1과 3 비교 → 1이 더 작음
현재 최솟값: 1 (확정)
최솟값 1과 첫 번째 원소 4를 교환
[1, 2, 4, 3]
✓ └─────┘
정렬됨 정렬 안됨
2단계: 두 번째 최솟값 찾기
[1, 2, 4, 3] ← 현재 최솟값: 2
✓ ↑_____↑
정렬되지 않은 영역
2와 4 비교 → 2가 더 작음
현재 최솟값: 2
2와 3 비교 → 2가 더 작음
현재 최솟값: 2 (확정)
최솟값 2는 이미 첫 번째 위치에 있으므로 교환 불필요
[1, 2, 4, 3]
✓ ✓ └──┘
정렬됨 정렬 안됨
3단계: 세 번째 최솟값 찾기
[1, 2, 4, 3] ← 현재 최솟값: 4
✓ ✓ ↑__↑
정렬되지 않은 영역
4와 3 비교 → 3이 더 작음
현재 최솟값: 3 (확정)
최솟값 3과 첫 번째 원소 4를 교환
[1, 2, 3, 4]
✓ ✓ ✓ ✓
정렬 완료
시각적 다이어그램
═══════════════════════════════════════════════════
초기 배열
═══════════════════════════════════════════════════
[4, 2, 1, 3]
↑ ↑ ↑ ↑
└──┴──┴──┘ 정렬되지 않은 영역 (전체)
═══════════════════════════════════════════════════
1단계: 최솟값 1 찾기
═══════════════════════════════════════════════════
[4, 2, 1, 3]
4 → 현재 최솟값
2 → 더 작음! (최솟값 갱신)
1 → 더 작음! (최솟값 갱신)
3 → 1보다 큼 (유지)
최솟값 1과 첫 원소 4 교환
[4, 2, 1, 3] → [1, 2, 4, 3]
↕ ↕
결과: [1 | 2, 4, 3]
✓ └─────┘
정렬됨 미정렬
═══════════════════════════════════════════════════
2단계: 최솟값 2 찾기
═══════════════════════════════════════════════════
[1 | 2, 4, 3]
2 → 현재 최솟값
4 → 2보다 큼 (유지)
3 → 2보다 큼 (유지)
최솟값 2는 이미 제자리에 있음 (교환 불필요)
결과: [1, 2 | 4, 3]
✓ ✓ └──┘
정렬됨 미정렬
═══════════════════════════════════════════════════
3단계: 최솟값 3 찾기
═══════════════════════════════════════════════════
[1, 2 | 4, 3]
4 → 현재 최솟값
3 → 더 작음! (최솟값 갱신)
최솟값 3과 첫 원소 4 교환
[1, 2, 4, 3] → [1, 2, 3, 4]
↕ ↕
결과: [1, 2, 3 | 4]
✓ ✓ ✓ ✓
정렬 완료
═══════════════════════════════════════════════════
비교 다이어그램: 버블 정렬 vs 선택 정렬
버블 정렬: 인접한 원소끼리 비교하며 큰 값을 뒤로 보냄
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[4, 2, 1, 3]
↕ 4 > 2 → 교환
[2, 4, 1, 3]
↕ 4 > 1 → 교환
[2, 1, 4, 3]
↕ 4 > 3 → 교환
[2, 1, 3, 4] ← 4 정렬 완료
선택 정렬: 최솟값을 찾아서 맨 앞으로 보냄
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
[4, 2, 1, 3]
└──┴──┴─→ 최솟값 1 발견
[4, 2, 1, 3]
↕ ↕ 첫 원소와 교환
[1, 2, 4, 3] ← 1 정렬 완료
Java 구현
public class SelectionSort {
/**
* 선택 정렬 알고리즘
* @param arr 정렬할 배열
*/
public static void selectionSort(int[] arr) {
// 외부 루프: 정렬되지 않은 영역의 첫 위치를 이동
// 마지막 원소는 자동으로 정렬되므로 n-1번 반복
for (int i = 0; i < arr.length - 1; i++) {
// 정렬되지 않은 영역에서 최솟값의 인덱스를 저장
int minValueIndex = i;
// 내부 루프: 정렬되지 않은 영역에서 최솟값 찾기
for (int j = i + 1; j < arr.length; j++) {
// 현재 값이 지금까지 찾은 최솟값보다 작으면 갱신
if (arr[j] < arr[minValueIndex]) {
minValueIndex = j;
}
}
// 찾은 최솟값을 정렬되지 않은 영역의 첫 번째 위치와 교환
int temp = arr[i];
arr[i] = arr[minValueIndex];
arr[minValueIndex] = temp;
}
}
// 배열 출력 메서드
public static void printArray(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
// 테스트 메인 메서드
public static void main(String[] args) {
int[] arr1 = {4, 2, 1, 3};
System.out.println("정렬 전:");
printArray(arr1);
selectionSort(arr1);
System.out.println("정렬 후:");
printArray(arr1);
}
}
/*
실행 결과
정렬 전:
[4, 2, 1, 3]
정렬 후:
[1, 2, 3, 4]
*/
시간 복잡도 분석
비교 횟수 계산
- 길이 n인 배열에서
- 1번째 패스: (n – 1)번 비교
- 2번째 패스: (n-2)번 비교
- 3번째 패스: (n-3)번 비교
- …
- 마지막 패스: 1번 비교
총 비교 횟수
(n-1) + (n-2) + (n-3) + … + 2 + 1
이는 등차수열의 합 공식으로 계산된다
n(n-1) n² - n
───────── → ────────
2 2
빅오 표기법
- 최고차항만 선택: n²
- 상수와 계수 제거: n²
- 시간 복잡도: O(n²)
간단하게 판별하는 방법은 중첩된 for문이 2개이므로 O(n²)
공간 복잡도
- O(1): 추가 메모리를 사용하지 않고 제자리에서 정렬 (in-place sorting)
장점
- 직관적이고 이해하기 쉬워서 구현이 간단하다
- 최대 n-1번의 교환만 발생하므로 교환 횟수가 적다
- 추가 메모리가 불필요한 제자리 정렬이다
- 최선 / 평균 / 최악의 경우 모두 O(n²)이라 일관된 성능을 제공한다
단점
- 시간 복잡도가 O(n²)이라 대용량 데이터에 비효율적이다
- 동일한 값의 순서가 바뀔 수 있는 불안정 정렬이다
- 이미 정렬된 배열도 O(n²)이라 최적화가 불가능하다
최적화
public static void selectionSortOptimized(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minValueIndex = i;
boolean isSorted = true;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minValueIndex]) {
minValueIndex = j;
isSorted = false;
}
}
// 이미 정렬된 경우 조기 종료
if (isSorted) {
break;
}
int temp = arr[i];
arr[i] = arr[minValueIndex];
arr[minValueIndex] = temp;
}
}
선택 정렬을 각 단계마다 최솟값을 선택해 앞으로 보내는 단순하고 직관적인 알고리즘이다. 교환 횟수가 적다는 장점이 있지만, O(n²)의 시간 복잡도로 인해 실무에서는 거의 사용되지 않는다.