[Algorithm/Java] 선택 정렬 (selection sort)

선택 정렬 (selection sort)

선택정렬은 대상 데이터에서 최대나 최소 데이터를 찾아서, 정렬 방법에따라 알맞은 위치로 이동시키는 방법이다.
선택정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)로 비효율적이기 때문에 잘 사용하지는 않지만, 응용해서 일부 사용할때도 있기 때문에, 방법은 알아두는것이 좋다.

---

핵심 이론

이 방법을 처음 접했을때 드는 생각은 굉장히 단순하고 비효율적이라는 생각이 들었다.

 

[ 5, 3, 1, 6, 4, 2]

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

위와 같은 정렬되지 않은 배열이 있을 때, 선택정렬을 이용하여 내림차순으로 정렬해보자.

1. 첫번째 사이클
   arr[0]에는 가장 큰수가 와야한다.
   arr[1]부터 arr[5]까지 모든 값들 중 가장 큰 수 max와 그 인덱스를 찾는다.
   만약 arr[0]보다 max 값이 크다면, arr[0]과 max값이 들어있는 인덱스를 서로 바꿔준다.
   그렇게되면 배열은 [ 6, 3, 1, 5, 4, 2] 가 될것이다.
2. 두번째 사이클
   arr[0]에는 가장 큰 수가 들어갔기 때문에, 이제는 arr[1]의 차례다.
   arr[2]부터 arr[5]까지 모든 값들 중 같은 방법으로 가장 큰 값을 찾고, arr[1]과 비교해서 값을 바꿔준다.
   그렇게되면 배열은 [ 6, 5, 1, 3, 4, 2] 가 될것이다.
3. 위의 과정을 반복한다.

---

Code

    for(int i=0;i<arr.length-1;i++){
            int max = 0;
            int maxIndex = 0;
            for(int j=i+1;j<arr.length;j++){
            //가장 큰 값 max와 그 index를 기억해둔다.
                if(max<arr[j]){
                    max = arr[j];
                    maxIndex = j;
                }
            }
            //max와 이번 사이클의 대상 값 arr[i]를 비교해서, 교환할지 말지 정한다.
            if(max>arr[i]){
                int temp = arr[i];
                arr[i] = max;
                arr[maxIndex] = temp;
            }
        }