선택 정렬(Selection Sort)

개념

주어진 값들 중 최솟값을 선택해서 배열의 맨 앞의 값과 교환한다. 그리고 맨 앞을 제외한 나머지 중에서 최솟값을 선택하고 교환하는 과정을 반복한다.

예제

{5, 4, 3, 2, 1} 로 이루어진 배열을 오름차순으로 선택 정렬하는 순서이다.

파란색 화살표는 주어진 범위에서 최소값이 위치할 공간을 가리키며, 빨간색 화살표는 최솟값을 가리킨다.

두 화살표가 가리키는 공간에 있는 값끼리 교환(swap)이 일어난다.

코드

class Sort {
    public static void selctionSort(int[] arr) {
        int min;
        int idx = 0;
        for (int i = 0; i < arr.length; i++) {
            min = Integer.MAX_VALUE;
            for (int j = i; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    idx = j;
                }
            }
            swap(i, idx, arr);
        }
    }

    public static void swap(int idx1, int idx2, int[] arr) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}

시간복잡도

5개의 숫자를 정렬하기 위해서 10번의 연산이 필요하다.

5 + 4 + 3 + 2 + 1

5 * ( 5 - 1 ) / 2 = 10

 

이를 일반식으로 표현하면

N + (N - 1) + (N -2) + ... + 3 + 2 + 1

N * (N - 1) / 2 

 

빅오표기법은 최고차항만을 표기하고 상수항은 무시하므로,

선택 정렬의 시간복잡도는 O(N^2) 이다.