선택정렬

선택정렬

배열(또는 리스트)의 첫 번째 원소에서 시작하여 배열 전체를 훑으면서 가장 작은 키를 가지는 원소를 찾아서 첫 번째 원소와 맞바꾼다. 두 번째 원소로 넘어감녀서 마지막 원소에 이르기까지 같은 작업을 반복한다. 

선택정렬의 효율

비교 횟수를 따져보면 첫 번째 원소를 맞바꿀 때 (n-1)번의 비교, 그 다음 두 번째 원소에서 (n-2)번의 비교,

.... 1번의 비교가 수행되며, (n-1) + (n-2) + ... + 1 이므로 n(n+1)/2임을 알 수 있다. 

따라서 선택 정렬의 알고리즘의 최선, 평균, 최악 모두 O(n^2)이다. 

    private static int[] selection_sort(int[] arr){
        for(int i = 0;i<arr.length;i++){
            int min_value = arr[i];
            for(int j = i;j<arr.length;j++){
                if(arr[j] < min_value){
                    arr = swap(arr, i, j);
                }
            }
        }
        return arr;
    }