선택 정렬 (Selection Sort)

1. 개념 설명

(1) 선택 정렬은 배열의 인덱스 위치를 정한 후, 가장 작은 원소를 넣으며 순차적으로 정렬하는 알고리즘이다.

 

 

 

 

2. 과정

by Gfycat

- 실제로 수행되는 과정이며, 맨 앞 인덱스부터 위치를 정한 후, 가장 작은 원소를 찾아서 넣는다.

 

by wiki

 

 

 

 

3. 코드

public class SelectionSort{
    public static void main(String[] args) {
        int[] A = { 7, 2, 8, 10, 1 };
        
        for(int i=0; i<A.length-1;  i++) {
            int index = i;
            
            for(int j=i+1; j<A.length; j++) {
                if(A[j]<A[index]) {
                    index = j;
                }
            }
            //swap
            int tmp = A[i];
            A[i] = A[index];
            A[index] = tmp;
        }
        
        System.out.println(Arrays.toString(A));
    }
}

 

 

 

 

4. 시간 복잡도

(1) 수행 횟수를 보면 (n-1) + (n-2) + ... + 2 + 1 --> n(n-1)/2가 나오게 된다.

 

(2) 그러므로, 선택 정렬에 시간 복잡도는 O(n²)이다.

( 시간 복잡도가 상당히 느리지만, 코드가 단순하므로 자주 사용된다고 한다. )

 

 

 

 

5. 공간 복잡도

(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.

 

 

 

 

6. 장점

(1) 버블 정렬과 같이 코드가 매우 단순하며 직관적이다.

 

(2) 정렬을 위한 비교 횟수는 많지만, 버블 정렬보다는 적기 때문에, 교환이 많이 일어나야 하는 자료 상태에서

비교적 효율적이다.

 

(3) 주어진 배열 안에서 정렬되기 때문에 다른 메모리 공간이 필요하지 않다.

( 제자리 정렬 (in-place sorting) )

 

 

 

 

7. 단점

(1) 시간 복잡도가 최선, 평균, 최악 모두 O(n²)이므로, 시간이 오래 걸리기 때문에 굉장히 비효율적이다.

 

(2) 불안정 정렬이다.