Sorting Algorithms - 선택 정렬(Selection Sort)

1. 정의

선택 정렬(Selection Sort)란, 배열의 가장 작은 요소부터 선택하여 알맞은 위치로 옮겨 정렬하는 알고리즘이다. 선택 정렬은 삽입 정렬과 유사하게 배열에서 정렬된 부분과 정렬되지 않은 부분이 존재한다.

2. 방식

배열에서 정렬되지 않은 부분의 가장 작은 값과 가장 앞에 있는 값을 교환하면 된다. 즉, 배열의 정렬되지 않은 부분의 첫 번째 값과 정렬되지 않은 부분의 가장 작은 값의 위치를 swap 해주면 되는 것이다.

3. 구현

바로 코드로 알아보도록 하자.

public class Main {
 
    public static void main(String[] args) {
 
        int[] array = {22, 5, 11, 32, 120, 68, 70, 6, 8, 1};
        Selection_Sort(array);
    }
 
    public static void Selection_Sort(int[] A) {
 
        int temp, min; // min은 배열 내에서 몇 번째 원소가 최소값인지 알기 위한 변수
        for(int i = 0; i < A.length - 1; i++) { // A.length - 1 까지인 이유는 어차피 마지막 원소는 자연스럽게 정렬된다.
            min = i;
            for(int j = i + 1; j < A.length; j++) { // 정렬이 안된 부분을 검사하는 반복문이므로 시작점은 i + 1 번째 부터이다.
                if(A[j] < A[min])  // 현재 위치(j)와 현재 기준 최소값(min)을 비교하여 현재 위치가 더 작은 경우, 최소값을 업데이트 해준다.
                    min = j;
            }
            temp = A[i];
            A[i] = A[min];
            A[min] = temp;
        }
 
        System.out.print("정렬 결과입니다 : ");
        for(int k : A) System.out.print(k + " ");
    }
}

정렬 결과입니다 : 1 5 6 8 11 22 32 68 70 120 

4. 결론

위의 결과가 코드와 정렬 결과이다. Selection Sort는 비교적 버블 정렬과 유사한 면을 띈다. 버블 정렬과 마찬가지로 모든 경우에서 시간복잡도 O(n²) 이다. 다만, 선택 정렬이 조금 더 빠르긴 하다.

선택 정렬은 비교적 간단한 편에 속하므로 우선 이정도로 정리하고 넘어가도록 한다.