선택 정렬 (Selection Sort)

1. 개요

• 자리를 먼저 정하고 들어갈 원소를 탐색한다.
• 한 번의 사이클이 끝나면 맨 앞자리부터 값이 확정된다.

---

2. 특징

• 구현이 간단하다.
• 교환하는 방식이기 때문에 추가적인 메모리를 사용하지 않는다. => 제자리 정렬(in-place sorting)
• 거품 정렬에 비해 swap 연산 횟수가 적다.
• 불안정 정렬이다.
• 시간복잡도: O(N^2)

---

3. 코드

import java.util.Arrays;

public class SelectionSortTest {

    public static void main(String[] args) {
        int[] arr = {3, 7, 2, 5, 1, 10};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

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

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}