[Sort] 선택 정렬(Selection Sort)

선택 정렬은 오히려 버블 정렬보다도 쉽고 간단한 알고리즘이다. 

1. 주어진 리스트 중에 최소값을 찾은 후, 

2. 그 값을 리스트 맨 앞에 위치한 값과 교체(교환)한다.

3. 맨 처음 위치를 제외하고(이미 최소값이므로) 나머지 리스트를 같은 방법으로 반복한다.

딱, 세가지만 생각하면 된다. 

① 주어진 리스트 중에 최소값을 찾는 방법

위와같은 배열a[]가 존재할 때, 리스트 중 가장 작은 요소의 인덱스값을 구하기 위해서는 어떻게 할까?

int[] arr = {3,5,1,7,9,2,6};

int min_index = 0;

for (int i = 1; i < arr.length; i++) {

if(arr[min_index]>arr[i]) min_index = i;

System.out.println(arr[min_index] +" "+arr[i]);

}

요런식으로 하면 인덱스 0(값6)이후의 값부터 비교해가며 최소값의 인덱스를 찾을 수 있다. 

min_index = 2일 것이다.

② 리스트 맨 앞 요소와 위치를 교환한다.

for (int i = 1; i < arr.length; i++) {

if(arr[min_index]>arr[i]) min_index = i;

System.out.println(arr[min_index] +" "+arr[i]);

//아래 부분이 추가됨.

temp = arr[0];

arr[0] = arr[min_index];

arr[min_index]= temp;

}

이러면 될까? 되긴 한다. 그렇지만 어떻게 나올까? 

1 5 3 7 9 2 6 

뭐야 이게? 뭐가 되긴 됐는데? 그렇다. 최소값 1이 맨 앞 3과 자리가 바꼈다....

근데. ㅡ_ㅡ;;;다른건 움직이지 않았다. 위 그림에서 보면 두번째 그림과 같다는 것을 알수 있다.

그래서 우리는 반복을 해주어 계속 정렬을 해야한다.

③ 리스트 맨 앞 요소를 제외한 리스트 전체를 위 과정을 반복실행 한다.

맨 앞 즉, 0번째 인덱스 정렬은. 끝났다. 1번째 인덱스부터 새롭게 시작한다. 그러면

min_index값은 어떻게 될까? 당연히.. 1부터다. 

즉, (배열의 크기-1)만큼 돌려야 모든 요소들이 비교를 해가면서 정렬이 완성될 것이다.(그림 참조)

for (int i = 0; i < arr.length; i++) {

for (int j = i+1; j < arr.length; j++) {

if(arr[min_index]>arr[j]) min_index = j;

temp = arr[i];

arr[i] = arr[min_index];

arr[min_index]= temp;

}

}

일단, ②에 나오는 for문을 감싸는 for문을 하나 더 삽입해서 이중for문이 되도록 해야 한다.

기존에 i변수를 j로 바꾸고 0번째 인덱스를 의미하는 0을 지우고 j를 넣는다.

왜냐하면 j가 하나하나 증가되면서 값을 저장하기 때문이다. 따라서,다음과 같이 정렬이 된다.

1 2 3 5 6 7 9 

선택 정렬의 성능평가 

버블 정렬과 성능상 큰 차이가 없다. 선택 정렬의 빅-오 역시 O(n^2) 

이 둘을 비교하는 것은 도토리 키재기..라고 할 수 있다.