[Java]정렬:선택정렬(Selection Sort)

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 5 2 6 3 4 7 8 9 10

---

위 문제에 대해서 정렬 알고리즘 중 "선택정렬(Selection Sort)"를 사용하여 

1 5 2 6 3 4 7 8 9 10   -> 1 2 3 4 5 6 7 8 9 10 

으로 정렬을 해보자.

 

선택 정렬은 쉽게 생각해서,
가장 작은 수를 선택해서 맨 앞으로 보내는 것!

package sort;

public class Selection_Sort {
    public static void main(String[] args) {

        int i,j,min,index=0,temp;

        int[] array = {1, 5, 2, 6, 3, 4, 7, 8, 9, 10};

        for (i = 0; i < 10; ++i) {
            min = 9999;
            for (j = i; j < 10; ++j) {
                if(min>array[j]){
                    min=array[j];
                    index=j;
                }
            }
            temp=array[i];
            array[i]=array[index];
            array[index]=temp;
        }

        for(i=0;i<10;++i){
            System.out.print(array[i]+" ");
        }
    }
}

i,j :  for 반복문을 위한 변수

min : 가장 작은 수를 일시적으로 담는 변수

index : 가장 작은 수가 위치 하고 있던 배열의 인덱스

temp : 가장 작은 수를 맨 앞의 수과 swap하기 위한 temporary변수

 

정상적으로 정렬이 되는 것을 확인할 수 있습니다.

 

---

하지만!!!

선택 정렬은 굉장히 비효율적인 정렬 알고리즘입니다. 생각해볼까요?

 

위 1 5 2 6 3 4 7 8 9 10 정렬하는 과정을 떠올려 봅시다.

First, 모든 1 5 2 .. 10 까지 모든 수를 반복문을 통해 비교해야하기 때문에 10번

(사람이 보기에는 1이 당연히 가장 작은 수이고, 맨 앞에 위치한 것이 보이지만 컴퓨터의 경우 1보다 작은 수가 있나, 없나 모두 확인해봐야합니다.)

 

Then, 맨 앞이 1임이 확정되었고, 5 2 6 .. 10 까지의 수를 탐색하는 9번의 비교 연산

 => 1 2 5 6 3 4 7 8 9 10

 

이렇게 계속 나아간다면, 10 + 9 + 8 + .. + 1 번의 비교 연산이 이루어지는 것을 알 수 있습니다.

수학적으로 표현하면, 10*(10+1)/2 번의 비교 연산이 수행되겠네요.

 

10번이 아니라 N번이라고 하여 선택정렬 알고리즘의 수행시간을 간단하게 표현하자면, 

N*(N+1)/2 번의 비교 연산이 수행될 것입니다.

 

이제 일반적으로 컴퓨터에서는 /2 나 +1 과 같은 경우는 N이 굉장히 크다는 가정하에 별 의미가 없기 때문에 간단하게 더하거나 나누는 연산들은 다 무시를 합니다. 그래서 N*N이라고 표현할 수 있습니다.

 

결과적으로 선택정렬(Selection Sort) 알고리즘의 수행시간은 Big-O로 나타내면,

선택 정렬(Selection Sort) 알고리즘의 시간 복잡도는
O(N^2)입니다!!

생각해볼까요?

알고리즘의 시간복잡도의 경우 극단적인 상황을 가정하면, 얼마나 빠른지 느린지 납득이 됩니다.

만약 N=10000이라면, 선택정렬은 대략적으로 총 1억번의 비교연산을 수행하는 것입니다.

즉, 굉장히 비효율적인 정렬방법이죠. 이후에는 버블정렬(Bubble Sort)를 공부해보도록 하겠습니다.