[알고리즘] 선택 정렬(Selection Sort)

다음 숫자들을 오름차순으로 정렬하시오.
2, 5, 4, 1, 3

---

선택 정렬은 가장 직관적인 정렬 방법이다. 숫자들 중 가장 작은 수를 제일 앞으로 보내는 방법으로 동작한다.

 

그림으로 살펴보자!

숫자들 중 가장 작은 1을 제일 앞의 2와 자리를 바꿨다.

가장 작은 자리를 찾았으니 다음으로 작은 숫자를 찾는다.

남은 숫자들 중에 가장 작은 2를 5와 교체한다.

다음 작은 수인 3과 4를 바꾼다.

마지막으로 4와 5의 자리를 바꾸면 오름차순으로 정렬된 것을 알 수 있다.

 

코드로 확인해보면,

 

public class Main {

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

        for(int i=0; i<5; i++) {
            int index = -1;
            min = Integer.MAX_VALUE;

            for(int j=i; j<5; j++) {
                if(min > arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }

        for(int i=0; i<5; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

정렬 방법만큼이나 연산 횟수(시간 복잡도, 데이터가 n개일 때 총 몇 번의 연산을 하는지)가 중요하다.

선택 정렬은 대략 $ n \times {\frac{n+1}{2}} $번 가량의 연산을 수행해야 한다. 즉,

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

 

다시 말해 데이터가 10,000개라면 약 1억 번 정도의 연산을 수행한다고 가정하겠다는 의미이다.