선택 정렬

 

 

1. 선택 정렬

 

 

선택 정렬은 다음과 같이 진행된다.

 

1. 주어진 숫자에서 최솟값을 찾는다.

2. 최솟값을 맨 앞자리 값과 바꾼다.

3. 맨 앞 자리를 제외한 나머지 값 중 최솟값을 찾아서 반복한다.

 

 시간복잡도 : O(N*N)

 

 

2. 그림으로 설명

 

다음과 같이 a배열이 있다고 하자.

즉, a[0] = 5 이다.

 

 

단계 1

 

 

1) min = 0 

 

i = 0 부터 시작한다.

즉, 위의 숫자 배열에서 맨 처음값부터 시작한다.

 

그리고 이때 min 이라는 변수를 사용하는데,

min = i 이다.

즉, 처음에 min = 0 이다.

 

j = i+1 = 1부터 시작한다.

그래서 혹시 

a[j] < a[min] 이라면,

min = j 로 바꿔준다.

 

 

 

즉,

a[1] < a[0]  이므로

min = 1 이 된다.

 

 

 

2) min = 1

 

 

min = 1, j = 2 이다.

 

역시 a[2] < a[1]  이므로

min = 2 로 바꿔준다.

 

 

3) min = 2

 

 

a[3] < a[2] 이므로

min = 3이 된다.

 

4) min = 3

 

 

 

min = 4 가 된다.

 

5) min = 4

 

 

이제 마지막까지 비교가 끝난다.

그러면 맨 처음 값 5와 a[min] 값을 바꿔준다.

 

6) 첫번째 값 확정

 맨 앞 값 1은 이제 위치가 확정된다.

 

 

 

단계 2

 

 

1) min = 1

 

 

이제 i = 1 이 된다.

즉, min = 1부터 시작한다.

그리고 j = i+1 = 2 가 된다.

 

즉, a[j] < a[min] 이라면

min = j 로 바꿔준다.

즉, 여기서 min = 2 가 된다.

 

 

 

2) min = 2

 

 

여기서 min = 3 이 된다.

 

3) min = 3

 

 

여기서는

a[j] > a[min]

이므로 min = 3

이 유지된다.

 

 

4) 두번째 값 확정

 

 

그러면 이제 두번째 값과 a[min] 값을 바꿔준다.

 

그러면 이제 1 2 3 4 5 순으로 숫자가 잘 정렬되어 있음을 볼 수 있다.

 

하지만 코드상으로는

i = 2 부터 즉

숫자 3부터 다시 min 값을 찾으면서 비교를 하게 된다.

 

그리고 i = 3까지 진행된다.

i = 4에서는 뒤에 더 이상 비교할 숫자가 없기 때문이다.

 

그래서 시간 복잡도는 O(N*N) 이 된다.

 

3. 최종 코드

 

import java.io.IOException;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		
		int a[] = {5,4,3,2,1};		
		int N = a.length;
		
		for(int i=0; i<N-1; i++) {
			
			int min = i;
				
			for(int j = i+1; j<N; j++) {
				
				if(a[j] < a[min]) {
					min = j;
				}	
			}
			
			int value = a[i];
			a[i] = a[min];
			a[min] = value;
			
		}
		
		System.out.println(Arrays.toString(a));
	}
}

 

 

참고 블로그 :

https://st-lab.tistory.com/168?category=892973