단순 선택 정렬

단순 선택 정렬이란? 가장 작은 요소를 맨 앞으로 이동시키고, 두번째 작은 요소는 맨 앞에서 두번째로 이동하는 등의 작업을 반복하는 알고리즘이다.
일단 처음부터 끝까지 한번 훑고 순서를 정해서 정렬시키는 방식으로 보면 된다.

어떠한 경우에서도 n(n-1)/2에 비례하는 시간이 걸리게 된다.

그럼에도 버블 정렬보다 보통 두 배 정도 빠르다.

버블 정렬과 같이 O(n^2)의 시간 복잡도를 가진다.

단순 선택 정렬 알아보기

	int[] arr = {6,4,8,3,1,9,7};

위 배열에 단순 선택 정렬 알고리즘을 적용해 보자. 이 알고리즘은 가장 작은 요소붙 정렬하기에 가장 작은 값의 요소인 1을 선택해 정렬을 시작한다.
1이 가장 작기에 1과 6(첫 요소)를 교환한다.

	int[] arr = {1,4,8,3,6,9,7};

배열의 상태는 위와 같아진다. 이어서 배열의 다음 작은수인 3을 선택하고 4(2번째 요소)와 교환한다.

	int[] arr = {1,3,8,4,6,9,7};

이런 방식으로 아직 정렬하지 않은 부분에서 가장 작은 요소를 선택하고, 아직 정렬하지 않은 부분에서 가장 첫 번째 요소와 교환하면 된다.

버블 정렬과 같이 요소수-1번만 실행하면 제일 큰 요소는 자동으로 마지막에 가 있게 돼 정렬이 끝난다.

정리

1. 아직 정렬하지 않은 부분에서 가장 작은 키값을 선택
2. 1번의 값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

※단순 선택 정렬은 서로 떨어져 있는 요소를 교환하기에 안정적이지 않다.

이를 바탕으로 간단히 코드를 짜보자.

예제

public class SimpleSelect { //단순 선택 정렬
    static void selectionSort(int[] a) {
        for (int i = 0; i < a.length-1; i++) {
            int min = i; // 정렬되지 않은 값 중 제일 작은 값
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min])
                    min = j;
            }
            swap(a, i, min); // 정렬되지 않은 값 중 첫번째 요소
        }
    }

    static void swap(int[] a, int idx1, int idx2) {
        int tmp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = tmp;
    }
}