선택 정렬

1부터 10까지 무작위로 정렬된 숫자들을 오름차순으로 정렬하는 방법엔 뭐가 있을까?

2 10 5 7 8 3 6 1 4 9

---

사람들은 생각할 필요도 없이 1부터 10까지 쭉 적어나가면 끝이다. 하지만 컴퓨터의 경우 그 과정을 알려주어야 한다. 즉, 알고리즘을 정의해주어야 하는것이다!

 

여러 정렬 알고리즘 중 선택정렬에 대해서 알아보도록 하자.

 

선택정렬의 키 아이디어는 "가장 작은것을 선택해서 제일 앞으로 보내자" 이다. 매우 직관적인 방법이라 할 수 있다!

 

 

1) 모든 원소를 순차적으로 돌았을 때 제일 작은 원소는 1임을 알 수 있다. 따라서 1을 첫번째 원소와 자리를 바꾼다.

 

1 10 5 7 8 3 6 2 4 9

 

2) 정렬된 첫번째 원소를 제외하고 순회했을 때 제일 작은 숫자는 2이다. 따라서 2를 두번째 원소와 자리를 바꾼다.

 

1 2 5 7 8 3 6 10 4 9

 

3) 2)와 같이 정렬된 1,2 를 제외하고 순회하여 제일 작은 숫자를 찾고 세번째 원소와 자리를 바꿔준다.

 

1 2 3 7 8 5 6 10 4 9

 

이렇게 정렬된 원소들을 제외하고 배열을 순회하면서 작은 숫자들을 찾아서 앞으로 보내면 정렬이 이루어지게 되는것이다!

---

자바로 구현한 소스코드이다.

/**
 * O(N^2)의 시간복잡도를 가진다.
 */
public class 선택정렬 {
    public static void main(String[] args) {
        int i;
        int j;
        int min;
        int idx = 0;
        int temp;

        int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        for (i = 0; i < 10; i++) {
            min = 9999;

            // 정렬이 끝난 인덱스는 순회하지 않는다.
            for (j = i; j < 10; j++) {

                // 배열을 순회하면서 가장 작은 원소를 찾는다.
                if (arr[j] < min) {
                    min = arr[j];
                    idx = j;
                }
            }

            // 가장 작은값을 찾았다면 제일 앞으로 보내준다.
            temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
        }

        for (int e : arr) {
            System.out.print(e + " ");
        }
    }
}

 

 min은 숫자들중 가장 작은 값을 저장하기 위한 변수이고 temp는 두 숫자의 위치를 바꿔주기 위한 변수이다.

---

알고리즘을 사용해야 할 땐 시간복잡도를 잘 생각해야한다.

 

선택정렬 시간 복잡도는 비교연산과 이동연산의 합으로 구해지는데,  데이터가 총 N개 일 때, 빅오 표기법으로 나타내면 O(N^2)의 시간복잡도를 갖는다. 

 

보통 1억번을 계산한다 했을 때 1초가 걸린다고 한다. 만약 데이터의 갯수가 10,000개 라면 O(N^2)의 시간복잡도를 갖는 알고리즘은 대략 1억번의 계산을 할 것이고 이는 1초를 넘어 갈 것이다. 만약 1초 미만의 시간을 요구한다면 선택정렬 대신 앞으로 만날 더 효율적인 알고리즘을 찾아야 할 것이다!