선택 정렬

매 pass마다 남은 원소 중 최솟값을 찾아 맨 앞으로 가져오는 정렬입니다.

동작 과정

[5, 3, 8, 1, 2]

pass 1: 최솟값 1 → 5와 교환  → [1, 3, 8, 5, 2]
pass 2: 최솟값 2 → 3과 교환  → [1, 2, 8, 5, 3]
pass 3: 최솟값 3 → 8과 교환  → [1, 2, 3, 5, 8] ← 5와 8이 뒤바뀜
pass 4: 최솟값 5 → 제자리    → [1, 2, 3, 5, 8]

구현

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

복잡도

• 불안정 정렬 X — 교환 시 같은 값의 순서 바뀔 수 있음
• in-place O
• 교환 횟수가 O(n)으로 최소 → 교환 비용이 클 때 유리

→ 정렬