[정렬] 선택 정렬

정렬

[정렬] 선택 정렬

kimyongjun0129 2025. 5. 1. 11:15

남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. (내림차순, 오름차순에 따라 다르다.)
정렬해야 하는 수의 갯수 : `n개` (n의 시간 복잡도)
하나를 정렬하는 데, 필요한 횟수 : 평균적으로 `1/2×n번` (n의 시간 복잡도, 상수는 무시된다.)
- 루프 첫 번째 : n 만큼 탐색
- 루프 두 번째 : n - 1 만큼 탐색
- .....
- 루프 n 번째 : n - n 만큼 탐색
따라서 `n × n` 이므로 총 시간 복잡도는 `n²` 이다.

핵심 이론

첫 번째 위치에서 시작하여 배열 끝까지 반복한다.
각 단계에서 가장 작은 값을 가진 요소의 인덱스를 찾는다.
그 인덱스의 값과 현재 위치의 값을 교환한다.
다음 위치(정렬이 안된 위치)로 이동하며 반복한다.

public void selectionSort(int[] arr) {
    int n = arr.length;

    // 배열의 처음부터 끝까지 반복
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 현재 위치를 최소값 인덱스로 가정

        // 나머지 요소 중에서 최소값을 찾음
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 최소값이 현재 위치와 다르면 교환
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

오름차순의 예이다. (정렬되지 않은 부분에서 최솟값을 구한 후, 왼쪽으로 옮겨야 한다.)
int j = i + 1 → 루프 한 번 돌 때마다, 한 칸 씩 정렬이 되기 때문이다.

[정렬] 선택 정렬

목차

선택 정렬

선택 정렬 특징

선택 정렬 수행 방식

핵심 이론