자바로 구현하는 선택정렬 (Selection Sort) 알고리즘

선택정렬이란?

 제자리 정렬 알고리즘의 하나로, 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식

1. 주어진 원소중 최소값을 찾는다.

2. 그 값을 첫 번째 원소와 교환 한다.

3. 그 다음 작은 원소를 찾아 다음 위치의 원소와 비교하여 교환한다.

위 과정을 반복하는 것이 선택정렬 입니다.

출처 - http://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

수도코드

예를들어, {80, 6, 2, 3, 1} 원소를 정렬하고자 하는 경우,

(기준위치 를 빨간색, 최소값 위치 파란색으로 표시)

1단계

  80 6 2 3 1

 정렬후 : 1 6 2 3 80

2단계

  1 6 2 3 80

정렬후 : 1 2 6 3 80

3단계

  1 2 6 3 80

정렬후 : 1 2 3 6 80

이렇게 기준위치와 최소값을 교체하는 방식으로 선택정렬이 완성 됩니다.

반대로, 내림차순의 경우 큰원소를 찾아 교환하면 되겠죠?

아래 자바코드를 구현해보면 아래와 같습니다.

자바코드

ASC (오름차순)

1.     public static int[] SelectionSortAsc(int[] items) {
2.         int indexMin, temp;
3.         for (int i=0;i<items.length-1;i++) {
4.             indexMin = i;
5.             for(int j=i+1;j<items.length;j++) {
6.                 //선택원소 보다 작은 원소위치 찾기
7.                 if (items[j] < items[indexMin]) {
8.                     indexMin = j;
9.                 }
10.             }
11.             temp = items[indexMin]; //최소값 임시 저장
12.             items[indexMin] = items[i]; //최소값 위치에 선택위치의 원소와 교환
13.             items[i] = temp; //선택위치에 최소값 교환
14.         }
15.         return items;
16.     }

DESC (내림차순)

1.     public static int[] SelectionSortDesc(int[] items) {
2.         int indexMax, temp;
3.         for (int i=0;i<items.length-1;i++) {
4.             indexMax = i;
5.             for(int j=i+1;j<items.length;j++) {
6.                 //선택원소 보다 큰 원소위치 찾기
7.                 if (items[j] > items[indexMax]) {
8.                     indexMax = j;
9.                 }
10.             }
11.             temp = items[indexMax]; //최대값 임시 저장
12.             items[indexMax] = items[i]; //최대값 위치에 선택위치의 원소와 교환
13.             items[i] = temp; //선택위치에 최대값 교환
14.         }
15.         return items;
16.     }

실행결과