[정렬] 선택 정렬

선택 정렬은 배열의 왼쪽부터 순서대로 정렬 구간을 확장하면서, 남은 구간에서 가장 큰(또는 작은) 값을 찾아 현재 인덱스 위치와 교환하는 방식의 정렬이다.

로직

1. 현재 위치i 를 기준으로 오른쪽 전체 구간에서 최대값(또는 최솟값)의 인덱스를 찾는다.
2. 찾은 인덱스의 값과 현재 위치의 값을 교환한다.
3. i를 하나 증가시키고 위 과정을 배열 끝까지 반복한다.

시간 복잡도 ⏳

• $O(n^2)$
• 데이터의 정렬 여부에 상관없이 동일한 비교 횟수를 가진다.

  선택 정렬은 교환 횟수가 적다는 장점이 있지만, 비교 횟수가 많기에 대규모 데이터에는 비효율적이다.

코드

public static void solution(int length, int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println((i + 1) + "번째 : " + Arrays.toString(arr));
        int maxIndex = i; // 현재 인덱스를 최대값으로 가정
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] > arr[maxIndex]) { // 더 큰 값 발견 시 갱신
                maxIndex = j;
            }
        }
        // 현재 인덱스(i)와 찾은 최대값 위치(maxIndex)를 교환
        int temp = arr[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

코드 플로우

1. for (int i = 0; i< arr.length; i++)
   →배열 전체를 돌며 내 위치i이후 구간 중 최대값을 찾는다.
2. int maxIndex = i;
   →일단 현재 위치를 최대값으로 세팅
3. 내부 루프

for (int j = i + 1; j < arr.length; j++) {
    if (arr[j] > arr[maxIndex]) maxIndex = j;
}

→i이후의 원소들은 모두 비교하면서 진짜 최대값의 인덱스를 찾음
4. 교환(Swap)

int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;

→가장 큰 값이 맨 앞으로 오도록 자리 바꿈
5. 반복
→i를 하나 늘려 다음 구간에서도 같은 과정 반복