선택 정렬

선택 정렬

선택 정렬은 전체 수를 조회하여 가장 작은 값을 맨 앞의 수와 교환하며 앞부터 채워나가는 정렬 방법입니다.

우선 제일 첫번째 자리, 즉 9가 있는 자리를 i라고 놓고 j는 i 다음부터 배열의 가장 작은 index(minIndex)를 뽑아 옵니다. j는 8부터 배열을 검색하면서 가장 작은 index를 찾아보니 1이 있는 자리가 제일 작군요. 그러니 minIndex는 2(1이 있는 배열 원소의 위치!)가 됩니다. 그래서 가장 첫번째 자리는 1이 되겠습니다.

그 후 두번째 자리(8이 있는 자리)가 i가 되고, j는 그다음 가장 작은 원소의 index를 구하게 되니까 minIndex는 2가 있는 자리, 즉 4가 됩니다. minIndex와 i를 바꿉니다

다음은 9가 있는 자리입니다. i는 2가 됩니다. 가장 작은 인덱스는 3이 있는 자리이므로 i와 바꾸어 줍니다.

다음 i가 하나 증가되어 9를 가리킵니다. 8이 더 작으니까 바꾸겠습니다.

이제 모든 비교와 교환은 끝났습니다. 오름차순으로 정렬이 된것을 볼 수 있습니다.

시간복잡도

이중 반복문 → $O(N^2)$

구현

class Solution {
    public int[] selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = 2147483647, idx = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    idx = j;
                }
            }
            // 앞의 최소값이 있어야할 자리에 이미 최소값이 있지 않은 경우
            if (i != idx) {
                nums[idx] = nums[i];
                nums[i] = min;
            }
        }
        return nums;
    }
}