매 라운드에서 최솟값을 선택해 앞으로 보내는 방식의 정렬 알고리즘이다.
1. 선택 정렬을 적용할 배열 생성 및 출력
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {3, 8, 4, 9, 2, 1};
System.out.println("정렬 전 : " + Arrays.toString(arr));
}
}정렬 전 : [3, 8, 4, 9, 2, 1]
2. 선택 정렬 메서드 정의
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {3, 8, 4, 9, 2, 1};
System.out.println("정렬 전 : " + Arrays.toString(arr));
selectionSortVisual(arr);
System.out.println("정렬 후 : " + Arrays.toString(arr));
}
// 선택 정렬 메서드
static void selectionSortVisual(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// i번째 위치부터 끝까지 최솟값의 인덱스를 찾음
int minIndex = i; // 현재 최솟값의 인덱스
System.out.println((i + 1) + "번째 인덱스 " + i + " ~ " + (n - 1) + "에서 최솟값 선택");
for (int j = i + 1; j < n; j++) {
System.out.printf("arr[%d] = %d vs 현재 최솟값[%d] = %d -> ", j, arr[j], minIndex, arr[minIndex]);
if (arr[j] < arr[minIndex]) {
minIndex = j;
System.out.println("최솟값 갱신 ! 새 최솟값 = " + arr[minIndex]);
} else {
System.out.println("유지");
}
}
// i번째와 최솟값 위치 교환
if (minIndex != i) {
System.out.printf("교환 : arr[%d] = %d <-> arr[%d] = %d%n", i, arr[i], minIndex, arr[minIndex]);
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
} else {
System.out.println("교환 없음");
}
System.out.println((i + 1) + "번째 완료 " + Arrays.toString(arr));
System.out.println();
}
}
}3. 동작 원리 설명
① minIndex 초기화
바깥쪽 루프에서 minIndex = i로 초기화한다.
여기서 minIndex는 값이 아닌 인덱스(위치)를 저장하는 변수이므로, arr[i]가 아닌 i로 초기화한다는 점에 주의한다.
즉, 현재 i 위치를 일단 최솟값의 위치라고 가정하고 시작한다.
② 안쪽 루프에서 최솟값 탐색
j는 i + 1부터 시작해서 배열 끝까지 순회한다.
arr[j]와 arr[minIndex]를 비교해 arr[j]가 더 작으면 minIndex = j로 갱신한다.
안쪽 루프가 끝나면 minIndex에는 i번째 이후 구간에서의 최솟값 인덱스가 담겨 있다.
③ 교환 (Swap)
안쪽 루프 종료 후, minIndex != i이면 arr[i]와 arr[minIndex]를 교환한다.
이미 최솟값이 제자리(minIndex == i)라면 교환하지 않는다.
④ 반복
위 과정을 n - 1번 반복하면 배열 전체가 오름차순으로 정렬된다.
4. 실행 결과
정렬 전 : [3, 8, 4, 9, 2, 1]
1번째 인덱스 0 ~ 5에서 최솟값 선택
arr[1] = 8 vs 현재 최솟값[0] = 3 -> 유지
arr[2] = 4 vs 현재 최솟값[0] = 3 -> 유지
arr[3] = 9 vs 현재 최솟값[0] = 3 -> 유지
arr[4] = 2 vs 현재 최솟값[0] = 3 -> 최솟값 갱신 ! 새 최솟값 = 2
arr[5] = 1 vs 현재 최솟값[4] = 2 -> 최솟값 갱신 ! 새 최솟값 = 1
교환 : arr[0] = 3 <-> arr[5] = 1
1번째 완료 [1, 8, 4, 9, 2, 3]
2번째 인덱스 1 ~ 5에서 최솟값 선택
arr[2] = 4 vs 현재 최솟값[1] = 8 -> 최솟값 갱신 ! 새 최솟값 = 4
arr[3] = 9 vs 현재 최솟값[2] = 4 -> 유지
arr[4] = 2 vs 현재 최솟값[2] = 4 -> 최솟값 갱신 ! 새 최솟값 = 2
arr[5] = 3 vs 현재 최솟값[4] = 2 -> 유지
교환 : arr[1] = 8 <-> arr[4] = 2
2번째 완료 [1, 2, 4, 9, 8, 3]
...
정렬 후 : [1, 2, 3, 4, 8, 9]5. 시간 복잡도
| 케이스 | 시간 복잡도 |
|---|---|
| 최선 | O(n²) |
| 평균 | O(n²) |
| 최악 | O(n²) |
- 비교 횟수 : n²/2번 → 바깥 루프 n번 × 안쪽 루프 평균 n/2번
- 교환 횟수 : 최대 n-1번 → 라운드마다 딱 1번만 교환
선택 정렬은 최선의 경우에도 항상 이중 루프를 돌기 때문에 O(n²)이다.
데이터 개수가 많을수록 성능이 급격히 떨어지므로, 소규모 데이터나 학습용으로 적합한 알고리즘이다.
6. 공간 복잡도
| 공간 복잡도 |
|---|
| O(1) |
temp, minIndex 같은 변수 몇 개만 사용하고 추가 배열을 만들지 않기 때문에 메모리를 거의 사용하지 않는다.
7. 특징
① 교환 횟수가 적다
라운드당 최대 1번만 교환하므로, 교환 비용이 비싼 상황(예: 디스크 I/O, 큰 객체 이동)에서 버블 정렬보다 유리하다.
② 이미 정렬된 배열도 O(n²)
최솟값을 찾는 비교 자체는 항상 수행되기 때문에 최적화가 불가능하다.
③ 불안정 정렬 (Unstable Sort)
같은 값의 상대적 순서가 바뀔 수 있다.
예를 들어 [3a, 3b, 1]을 정렬하면 3a와 3b의 순서가 뒤바뀔 수 있다.
안정 정렬이 필요한 경우에는 삽입 정렬이나 병합 정렬을 사용해야 한다.
