선택정렬 정리

 

선택정렬이란 '가장 작은 것을 선택해서 앞으로 보내는 정렬 알고리즘'입니다.

 

예를들어, 1 10 5 8 7 6 4 3 2 9 라는 수가 있고 이것을 1 2 3 4 5 6 7 8 9 10으로 정렬하고 싶을 때 선택정렬을 이용할수 있습니다.

public class SelectionSort {
    public static void main(String[] args) {
        int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        selectionSort(array);
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
    
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

selectionSort 메소드를 보면 먼저 1) 배열의 첫번째 번호(i)를 인덱스로 선언하고,

2) 두번째 값부터 마지막 값을 첫번째 값과 비교합니다.

3) 비교된 값 중 작은 값의 배열 번호를 인덱스로 설정하고, 첫번째 번호(i)의 값과 인덱스 번호의 값을 swap합니다.

 

다음으로, 두번째 배열번호(i)를 똑같이 인덱스로 선언하고 세번째 값부터 2),3)과 같은 논리로 진행됩니다.

 

이와같이 끝까지 진행하면 첫번째 과정에서 9번 순회를 하고,

두번째 과정에서 8번,

세번째 과정에서 7번...순으로 9+8+7+6+5+4+3+2+1 = 36 번 진행하게 됩니다.

 

이러한 계산 과정은 배열의 크기에 따라 등차수열 값으로 표현 할 수 있습니다.

배열의 크기가 n이라면 n(n-1)/2 꼴로 나타낼수 있으며,

가장 큰 차수가 값이 커질수록 늘어나는 폭이 제일 크기에 나머지는 상수라고 봐도 되기에 n의 2차 라고 볼수 있습니다.

 

그래서 시간복잡도는 O(n^2)가 됩니다.

시간 복잡도는 클수록 안좋은 알고리즘이며, 선택정렬은 이러한 복잡도 측면에서는 좋지 못한 알고리즘이 됩니다.