선택정렬(Selection srot) 알고리즘

선택정렬(Selection Sort)

선택정렬은 제자리 정렬 알고리즘의 하나 입니다. 

주어진 배열은 정렬 된 부분과 정렬되지 않는 부분으로 나누어 다음과 같은 방법으로 정렬 합니다. 

1) 정렬 되지 않은 부분에서 최소(또는 최대)의 요소를 찾습니다.

2) 정렬 되지 않은 부분의 첫번째 위치와 위에서 찾은 요소를 교환 합니다.

3) 모든 배열이 정렬 될 때 까지 위의 과정을 반복합니다.

첫번째 루프에선 배열 전체가 정렬 되지 않은 부분 이므로 arr[0...9] 에서 최솟값을 찾아 정렬되지 않은 부분의 첫 요소 arr[0] 와 교환 합니다.

                            최솟값

12

1

32

45

77

11

23

49

21

100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]

두번째 루프에선 이미 정렬된 요소 arr[0] 을 제외한 나머지 부분 arr[1...9] 최솟값을 찾아 정렬되지 않은 부분의 첫 요소 arr[1] 와 교환합니다.

                                                                                                                                                                               최솟값

1

12

32

45

77

11

23

49

21

100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]

위와 같은 방법으로 정렬되지 않은 부분에서 최솟값을 찾아 정렬되지 않은 부분의 첫 요소와 계속 교환하는 방식으로 모든 배열을 정렬 할 수 있습니다.

                                                                                                                                                                               최솟값

1

11

12

21

23

32

77

49

45

100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]

다음은 자바로 구현한 선택정렬 입니다.

    // 선택정렬 알고리즘은 정렬되지 않은 부분에서 최소(또는 최대) 요소를 찾아
    // 정렬되지 않은 배열의 첫인덱스에 값을 넣어 배열을 정렬한다.
    // 즉, 선택정렬에선 두 개의 서브 어레이를 유지한다.
    // 1) 정렬 된 부분
    // 2) 정렬 되지 않은 부분
    // 시간 복잡도 O(n^2)
 
    // 배열의 요소를 교환 해주는 메소드.
    public void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
 
    void selectionSort(int arr[]) {
    
        int min;
 
        for (int i = 0; i < arr.length - 1; i++) {
            // 정렬 되지 않은 부분의 첫번째의 인덱스 값을 최솟값(또는 최대)으로 설정한다.
            min = i;
            // 정렬 되지 않은 부분의 최소 요소를 찾는다.
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[i]) {
                    min = j;
                }
                // 정렬 되지 않은 부분의 첫인덱스와 최소요소를 교환한다.
                swap(arr, j, i);
            }
        }
    }