1. 선택 정렬 (Selection Sort)

다음 숫자들을 오름차순으로 정렬하는 알고리즘을 작성하시오.
1  10  5  8  7  6  4  3  2  9

가장 간단하면서도 쉽게 떠오르는 방법으로 알고리즘을 작성해봅시다.

 

배열을 탐색하여 가장 작은 값을 앞으로 보내면 어떨까?

 

순차적으로 가장 작은 숫자를 탐색해 맨 앞쪽과 자리를 바꾸어 줍니다.

가장 기초적이고 원시적인 선택정렬 알고리즘입니다.

 

소스코드

public class TestMain {
    public static void main(String[] args) {
        int[] array = {1,10,5,8,7,6,4,3,2,9};
        for(int i=0;i<10;i++){
            int min =999, idx = i;
            for(int j=i;j<10;j++){
                if(array[j] < min){
                    idx = j;
                    min = array[j];
                }
            }
            int temp = array[i];
            array[i]= array[idx];
            array[idx] = temp;
        }

        for(int i:array){
            System.out.print(i+" ");
        }
    }
}

 

결과

1 2 3 4 5 6 7 8 9 10 

 

 

데이터 갯수가 N일 때, 총 연산 횟수는 N*(N+1)/2 입니다.

N + (N-1) + (N-2) + ...... + 2 + 1 = N*(N+1)/2

 

따라서 시간복잡도는 O(N^2) 입니다.

 

N이 10만 이 되면 10^10, 100억번의 연산이 필요합니다. 따라서 선택정렬은 굉장히 비효율적인 알고리즘이라고 볼 수 있겠습니다.