선택 정렬 (Selection Sort)

출처: 위키백과

 

정의

자리를 정해두고 해당 자리에 들어올 값을 선택하는 알고리즘이다.

선택 정렬의 '선택'은 들어올 값을 선택하는 것이라고 생각하자.

 

설명

[5, 4, 3, 2, 1]

위 배열을 오름차순 정렬해보자.

 

자리를 순회하며 해당 자리에 올 값을 찾아 넣는다.

값을 찾는 방법은 해당 자리에 위치해있던 값과 나머지 모든 값을 비교한다.

 

1. 첫번째 자리에 올 값 선택

오름차순 정렬이니, 첫번째 자리에는 1이 와야한다.

5를 제외한 나머지 모든 수 [4, 3, 2, 1] 을 순회하여 가장 작은 값인 1을 찾아 5와 바꾼다.

 

[1, 4, 3, 2, 5]

 

2. 두번째 자리에 올 값 선택

두번째 자리에는 두번째로 큰 값인 2가 와야한다.

1과 4를 제외한 나머지 모든 수 [3, 2, 5] 을 순회하여 가장 작은 값이 2를 찾아 4와 바꾼다.

 

[1, 2, 3, 4, 5]

 

3. 세번째 자리에 올 값 선택

위 수는 이미 오름차순으로 정렬되었지만, 선택정렬은 순차적으로 모든 자리 수를 순회하기 전까지 종료할 방법이 없다.

따라서 모든 자리 수를 같은 방법으로 순회하여 값을 선택해야 한다.

 

복잡도

 

	시간 복잡도	공간 복잡도
Best	N^2	N
Worst	N^2	N
Avg	N^2	N

 

시간복잡도는 모든 경우에서 N^2이다.

자리를 순회하는 반복(N) 마다 값을 선택하는 반복(N)을 해주어야 하기 때문이다.

 

공간복잡도는 N이다.

매 반복마다 Swap을 통한 메모리 공간을 1회씩 사용하므로 N이다.

 

구현

public class SelectionSort {

    public static void main(String[] args) {
        int[] array = new int[] {5, 2, 3, 4, 1};

        print(array);
        sort(array);
        print(array);
    }

    private static void sort(int[] array) {
        int minIndex = 0;
        int temp;

        for (int i = 0; i < array.length; i++) {
            minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        System.out.println("");
    }
}