[Algorithm] 2-2 Selection Sort(선택 정렬)

정렬 알고리즘
1. Bubble Sort(거품 정렬)
2. Selection Sort(선택 정렬) ⇠
3. Insertion Sort(삽입 정렬)
4. Quick Sort(퀵 정렬)
5. Merge Sort(병합 정렬)
6. Heap Sort(힙 정렬)
7. Radix Sort(기수 정렬)
8. Counting Sort(계수 정렬)

기본 개념

• 평소 무언가를 크기 순으로 나열할 때 흔히 사용하는 방식이다.
• 크기 n의 배열이 주어졌을 때, index 0부터 n-1까지의 모든 index i에 대해서, i번째 부터 n-1번째까지 값 중 가장 작은 값을 구해서 index i에 놓으면 정렬된 배열을 얻을 수 있다.
• 정렬되지 않은 배열에서 최솟값을 선택해 정렬되지 않은 배열의 첫번째 인덱스에 넣어준다.
• 모든 index에 대해서 해당 index에 놓을 값을 선택하기 때문에 선택 정렬, Selection Sort라고 부른다.

특징

• 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 된다. 따라서, 뒤에 있는 index로 갈수록 비교 범위가 하나씩 점점 줄어드는 특성을 가지고 있다.
• 입력 배열의 정렬 여부와 관계없이 동일한 연산량을 가지고 있기 때문에 최적화 여지가 적어서 동일한 시간복잡도(O(n^2))를 가지고 있는 알고리즘에 비교해도 성능이 떨어지는 편이다.
• 가장 구현이 쉬운 정렬 알고리즘이다.

구현(Java)

public class Selection {
	public static void sort(int[] arr) {
    	// 제일 마지막 순서(n)은 n-1번째가 정렬되는 순간 자동 정렬되므로 n-1까지만 탐색
    	for (int i = 0; i < arr.length-1; i++) {
        	int minIdx = i;
            for (int j = i+1; j < arr.length; j++) {
            	if (arr[j] < arr[minIdx]) {
                	minIdx = j;
                }
            }
            swap(arr, i, minIdx);
        }
    }
    
    private static void swap(int[] arr, int a, int b) {
    	int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

복잡도

• 공간복잡도 : 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1) 의 시간복잡도를 가진다.
• 시간 복잡도 : loop를 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N) 의 시간을 소모하며, 하나의 loop에서는 현재 인덱스의 값들과 비교하여 최소값을 찾은 후 현재 인덱스에 있는 값과 자리 교대(swap)을 해야하므로 O(N) 의 시간이 필요하게 된다. 따라서, 총 O(N^2) 의 시간 복잡도를 가진다.