[Java] 배열의 활용 : 정렬하기 - 선택정렬(selection sort)

 

 

 

<선택 정렬의 정의>

 

오름차순의 경우,

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면

선택 정렬은 1회 차에

1번부터 끝까지 훑어서 최소값을 1번 요소에 정렬하고,

2회 차에 2번부터 끝까지 훑어서

그다음 작은 값을 2번 요소에 정렬하는 것을 

(n-1)번 반복한다.

 

어찌 보면 인간이 사용하는 정렬 방식을 가장 많이 닮았다.

 

 

 

▼ 참고 영상

 

 

 

<선택 정렬의 원리>

 

버블 정렬에서 사용한 배열로 

선택 정렬을 하면 다음과 같다.

 

int[] numArr = new int[] { 5, 1, 3, 4, 2 };

 

(i=0) 1회 차에 
(j=0~4) { 5, 1, 3, 4, 2 } 배열 중

　　　 최소값이 있는 요소를 찾아

　　　 0번에 있는 값과 교환하여

　　　 0번에 최소값을 정렬한다.

　　　 { 1, 5, 3, 4, 2 } 

(i=1) 2회 차에 

(j=1~4) 이미 정렬된 0번을 제외하고
　　　 1번부터 최소값이 있는 요소를 찾아

　　　 1번에 있는 값과 교환하여

　　　 1번에 그다음 최소값을 정렬한다.

　　　 { 1, 2, 3, 4, 5 } 　　 

(i=2) 3회 차에 

(j=2~4) 이미 정렬된 0번과 1번을 제외하고

　　　 2번부터 최소값이 있는 요소를 찾아

　　　 2번에 있는 값과 교환하여

　　　 2번에 그다음 최소값을 정렬한다.

　　　 해당 배열은 2번 요소에 저장된 값보다

　　　 작은 값이 3~4번 요소에 없으므로

　　　 회차를 마친다.

　　　 { 1, 2, 3, 4, 5 } 

(i=3) 4회 차에

(j=3~4) 이미 정렬된 0~2번을 제외하고

　　　 3번부터 최소값이 있는 요소를 찾아

　　　 3번에 있는 값과 교환하여

　　　 3번에 그다음 최소값을 정렬한다.

　　　 해당 배열은 3번 요소에 저장된 값보다

　　　 작은 값이 4번 요소에 없으므로

　　　 회차를 마치고 

　　　 { 1, 2, 3, 4, 5 } 

　　　 최종적으로 선택 정렬을 마친다.

 

버블 정렬보다는 좀더 빠르게 정렬을 마칠 수 있다.

 

<선택 정렬 코딩>

 

Java에서 버블 정렬의 오름차순을 코딩하면 다음과 같다.

 

public class P204_Array_SelectionSort {
	public static void main(String[] args) {
		int[] numArr = new int[10];			// 길이가 10인 배열 선언 및 생성
		for (int i = 0; i < numArr.length; i++) {	// 배열에 0~9사이의 임의의 수 저장
			System.out.print(numArr[i] = (int)(Math.random() * 10));
		}
		System.out.println();

		for (int i = 0; i < numArr.length-1; i++) {
			int minPos = i;				// 최소값이 저장된 인덱스 위치
			for (int j = i + 1; j < numArr.length; j++) {
				if(numArr[minPos] > numArr[j]) {	// --- ①
					minPos = j;
				}
			}
			int tmp = numArr[i];
			numArr[i] = numArr[minPos];
			numArr[minPos] = tmp;
		}
		for (int k = 0; k < numArr.length; k++)
			System.out.print(numArr[k]); 		// 정렬된 결과를 출력
		System.out.println();
	}
}

① numArr[pos] < numArr[j]와 같이

　 부등호의 방향을 바꾸면

　 최대값을 찾아 정렬하므로

　 내림차순이 된다.