[JAVA] 선택정렬(Selection Sort) 알고리즘

선택정렬(Selection Sort)

선택정렬은 배열중에 가장 작은 원소들을 왼쪽부터 채워나가면서 숫자를 정렬하는 방법입니다.

최소원소를 찾은 후 

=> 최소원소를 맨 왼쪽원소와 교환(즉, 왼쪽부터 정렬된 원소로 채워집니다.)

=> 왼쪽원소를 제외하고 원소가 하나남을때 까지 이단계를 반복

(그림 참고)

선택정렬의 비교횟수를 구해보면

1단계 => n개의 원소 비교

2단계 => n-1 개의 원소 비교

3단계 => n-2 개의 원소 비교

....

를 하여 비교 횟수는

n(n-1) /2 가 됩니다.

즉, 시간복잡도는 O(n^2)이 됩니다.

   // 선택정렬 
    public void selectionSort(int[] array) {
        int size = array.length;
        int i, j, min;
        
        for(i = 0; i < size-1; i++) {
            min = i;
            for(j = i+1; j < size; j++) {
                if(array[j] < array[min]) {
                    min = j;
                }
            }
            swap(array, min, i);
            System.out.printf("\nSelectionSort %d 단계 : ", i+1);
            for(j = 0; j < size; j++) {
                System.out.printf("%3d", array[j]);
            }
        }
    }
    
    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }