[정렬 뿌시기] - 선택정렬(Selection Sort)

선택 정렬(Selection Sort)란?
가장 작은 값을 찾아 맨 앞부터 순차적으로 정렬하는 방법

선택 정렬의 알고리즘은?

(1) 1번과 2번 원소를 비교

(2) 1번과 3번 원소를 비교

(3) 1번과 4번 원소를 비교

(4) 1번과 5번 원소를 비교

(5) 1번과 2~5번 원소를 비교하여 가장 작은 값을 가진 원소의 인덱스를 기억하여 첫 번째 인덱스와 값을 변경한다.

(6) 2번과 3번 원소를 비교

(7) 2번과 4번 원소를 비교

(8) 2번과 5번 원소를 비교

(9) 2번과 3~4번 원소를 비교하여 가장 작은 값을 가진 원소의 인덱스를 기억하여 두 번째 인덱스와 값을 변경한다.(자기 자신이 가장 작은 값일 경우 그대로 유지)

위와 같이 순차적으로 앞에서 부터 정렬시켜 나가는 방법을 선택 정렬이라 한다. 위의 내용에서 첫 번째와 두 번째는 이미 정렬되어 가장 작은 수로 판단되었으므로 이후 정렬 연산에는 참여할 필요가 없다.

선택 정렬을 자바 코드로 구현해보기

public class selectionSort {

    static int[] arr = {3, 2, 5, 4, 1};

    public static void main(String[] args) {

        int min_idx ;
        for(int i=0; i<arr.length - 1; i++){
            min_idx = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[min_idx] > arr[j])
                    min_idx = j;
            }
            swap(min_idx, i);
        }
        printArray();
    }

    private static void swap(int min_idx, int cur_idx) {

        int temp = arr[cur_idx];
        arr[cur_idx] = arr[min_idx];
        arr[min_idx] = temp;

    }

    public static void printArray(){

        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ");
        }

    }

}

선택 정렬을 자바 코드로 구현해보기(재귀)

public class selectionSort {

    static int[] arr = {3, 2, 5, 4, 1};

    public static void main(String[] args) {
        selectionSrot();
        printArray();
    }

    private static void selectionSrot() {
        selectionsort( 0);
    }

    private static void selectionsort( int start){
        if(start < arr.length-1){
            int min_idx = start;

            for(int i=start+1; i<arr.length; i++){
                if(arr[min_idx] > arr[i])
                    min_idx = i;
            }
            swap(min_idx, start);
            selectionsort(start+1);
        }
    }

    private static void swap(int min_idx, int cur_idx) {

        int temp = arr[cur_idx];
        arr[cur_idx] = arr[min_idx];
        arr[min_idx] = temp;

    }

    public static void printArray(){

        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ");
        }

    }

}

버블 정렬과 다른 점이 있다면 순차적으로 모든 값을 비교하는 것은 같지만 swap 연산은 단 1번만 일어난다는 것이 다르네요. 그 차이 때문인지 버블 정렬보다 선택 정렬의 효율이 더 뛰어납니다.

선택 정렬의 시간복잡도
선택 정렬의 소스코드를 보면 가장 작은 값의 인덱스를 찾기 위해 n-1번의 비교를 합니다. 그 후에는 n-2, n-3,... 1번이 됩니다! 그러므로 시간 복잡도는 n-1 + n-2 + n-3 +... 1 = n(n-1)/2 = O(n^2)이 됩니다.

출처 : https://www.youtube.com/watch?v=uCUu3fF5Dws