선택 정렬 (Selection Sort)
선택 정렬은 배열의 맨 앞부터 차례로, 한 칸씩 뒤로 가며 해당 위치에 올바른 값을 선택하여 채워나가는 정렬 알고리즘입니다.
배열명을 arr이라고 한다면,
arr[0]을 찾기 위해 arr[1]부터 arr[n]까지의 값 중
가장 작은 값 (혹은 큰 값)을 찾아 그 값을 arr[0]과 바꿔줍니다.
그다음 arr[1]을 앞선 방식과 동일하게 arr[2]부터 끝까지 탐색하여 값을 찾아 바꿔줍니다.
이 과정을 마지막 인덱스 - 1까지 반복하면 배열이 정렬됩니다.
결국n-1번, n-2번, … , 1번비교를 진행하므로
시간 복잡도는O(n2)입니다.
예시 코드 (Java)
자바를 사용한 오름차순 선택 정렬 예제입니다.
// Selection Sort in Java
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {3, 2, 5, 1, 7};
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int tmp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tmp;
}
// 결과: 1, 2, 3, 5, 7
}
}
정리
- 선택 정렬은 최선, 평균, 최악 모두 시간복잡도
O(n²) - 교환(swap) 횟수가 적다 → 버블 정렬보다 효율적
- 데이터 양이 많아질수록 느리다는 단점
