선택 정렬

 

선택 정렬은 데이터들 중에서 가장 작은 데이터를 선택한 뒤, 가장 맨앞에 있는 데이터와 바꾸는 정렬방법이다.

 예를들어 위와 같은 그림이 있다고 가정하자.

그러면 가장 작은 값을 선택한다. 가장 작은 값은 1이다.

그러므로 움직이지 않는다.

이 자리는 이제 정렬이 된 상태이므로 더 이상 움직일 필요는 없다.

만약 3처럼 움직여야 되는 상황이라면, 두 번째 숫자인 7과 자리를 바꾸면 된다.

그리고 3도 역시 더 이상 움직이지 않는다.

이제 이와 같은 방법으로 진행하면 자연스럽게 정렬이 되어 있다.

 

 하지만 이 정렬의 가장 큰 문제점은 느리다는 점이다.

'그 이유는 가장 작은 값을 찾기 위해 마지막 까지 가야 비로서 찾을 수 있기 때문이다.

즉, 100개끝에 가장 작은 번호가 있을 경우, 100번까지 도달해야 된다는 의미다.

결국은 시간 복잡도는 O(n^2)걸리게 된다고 한다.

그렇기 때문에 이 방법은 굉장히 단순하지만 굉장히 오래걸린다는 문제점을 안고 있다.

그러면 자바 코드로 구현을 해보겠다.

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] array = {7,5,9,0,3,1,6,2,4,8};

        for(int i = 0;i<array.length;i++) {
            int min_index = i;
            for(int j = i+1; j<array.length;j++) {
                if (array[min_index] > array[j]) {
                    min_index = j;
                }
            }
            // 스와프
            int temp = array[i];
            array[i] = array[min_index];
            array[min_index] = temp;
        }

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

 

스와프는 나중에 따로 올리는 게 좋을 것 같다.