[정렬]03. 선택정렬

1.기본 컨셉

 - 정렬되지 않은 배열 중에서 최소값을 찾아 정렬되지 않은 맨 처음 요소와 자리를 바꾼다.

 - 이제 자리를 바꾼 요소는 정렬된 요소이다.

 - 하나의 원소만 남을 때까지 위 과정을 반복한다.

 

아래의 동영상을 살펴보자.

https://www.youtube.com/watch?v=Ns4TPTC8whw

 

2. 정렬 과정

 

3. 자바 코드

@Test
public void selectionSortTest(){
	data = new int[] {3,0,1,8,7,2,5,4,9,6};
	for(int i=0; i<data.length; i++) {
		int base = data[i];
		
		int min = Integer.MAX_VALUE;
		int minI = -1;
		for(int j=i; j<data.length; j++) {
			if(data[j]<min) {
				min = data[j];
				minI = j;
			}
		}
		if(min!=base) {
			data[i]=min;
			data[minI]=base;
		}
		System.out.printf("%d번째: %s%n", i, Arrays.toString(data));
	}
	System.out.printf("정렬 완료: %s%n", Arrays.toString(data));
}

 

0번째: [0, 3, 1, 8, 7, 2, 5, 4, 9, 6]
1번째: [0, 1, 3, 8, 7, 2, 5, 4, 9, 6]
2번째: [0, 1, 2, 8, 7, 3, 5, 4, 9, 6]
3번째: [0, 1, 2, 3, 7, 8, 5, 4, 9, 6]
4번째: [0, 1, 2, 3, 4, 8, 5, 7, 9, 6]
5번째: [0, 1, 2, 3, 4, 5, 8, 7, 9, 6]
6번째: [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
7번째: [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
8번째: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9번째: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
정렬 완료: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4. 정리

시간 복잡도는 O(n^2)로 버블정렬, 삽입 정렬 처럼 구현은 단순하지만 비효율적인 방법이다.