선택정렬(Selection Sort)

개념

• 선택이라는 말 그대로 배열의 요소 중 가장 작은 값 (또는 가장 큰 값)을 선택하여 앞으로 하나씩 가져오는 정렬
• 앞으로 자리를 교환한 요소 다음 요소부터 배열을 검사하여 위의 절차를 반복한다.
• K 번째 반복시 K 인덱스 부터 배열의 요소를 모두 비교하여 가장 작은 값 (또는 가장 큰 값)을 선택하여 K 인덱스의 요소와 서로 교환한다.

예제

• 배열의 크기가 10인 0~9의 데이터가 저장되어 있는 배열을 K 번(0~9 번) 반복하여 정렬한다.

 

1. K 번째 요소와 K 인덱스 부터 배열의 끝 부분 까지 모두 검사하여 가장 작은 값의 인덱스를 저장한다.
2. K 번째 요소와 저장된 인덱스의 값을 서로 교환한다.
3. K 를 1 증가시켜 위의 과정을 반복한다.

gif로 보는 선택정렬 [출처 : https://github.com/GimunLee]

코드

public void selectionSort(int[] arr) {
        for(int i = 0; i<arr.length; ++i) {
            int idx = i;
            for(int j = i; j<arr.length; ++j) {
                idx = (arr[j] < arr[idx])? j : idx;
            }

            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
    }

 

장점

1. 대체로 버블정렬보다 약간 더 좋은 성능을 기대할 수 있다.
2. 삽입정렬과 같이 정렬하려는 배열의 크기가 작을때 효율적이다.

단점

1. 불안정 정렬이다.
2. 적절한 인덱스를 찾기위한 탐색만을 하는 삽입정렬과 달르게 모든 요소를 탐색하기 때문에 성능이 상대적으로 좋지 않다.

시간복잡도

• 최적, 최악, 평균 모두 시간복잡도가 O(n^2) 로 동일하다.
• 요소 탐색시 최대값과 최솟값을 동시에 찾는다면 반복횟수를 절반으로 줄일 수 있다.

정리

• 코드가 단순하고 시간복잡도가 O(n^2) 인 정렬 중에서 버블정렬보다는 빠르다.
• O(nlogn) 과 달리 이미 정렬되어 있을 때 탐색 외의 작업을 하지 않기 때문에 삽입정렬과 같이 이미 정렬되어 있는지 확인하는 방법으로 쓰이기도 한다.

 

출처

• https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html
• https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%84%A0%ED%83%9D%20%EC%A0%95%EB%A0%AC%20(Selection%20Sort).md#%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-selection-sort