[ 알고리즘 ] 선택 정렬 (Selection Sort)

선택정렬이란?

처음 배열 탐색 시 최소값을 찾은 후 가장 첫번째 배열값과 자리를 바꾸는 방식.

 

 

시간복잡도

O(n^2)이며 큰 데이터셋에는 적합하지 않다. 따라서 큰 데이터셋에는 퀵, 힙, 병합정렬등을 고려.

 

 

선택정렬 흐름도

1. 배열내 최솟값을 찾음
2. 최솟값을 맨앞자리 값과 swap
3. 이미 자리교체된 값의 다음값을 첫번째로 기준으로 삼고 1,2 번 과정 반복
4. round 9는 8번돌면 최종적으로 마지막 값은 정렬이 되있으므로 skip 

 

 

 

자바 구현

public class Selection_Sort {
 
	public static void selection_sort(int[] a) {
		selection_sort(a, a.length);
	}
	
	private static void selection_sort(int[] a, int size) {
		
		for(int i = 0; i < size - 1; i++) {
			int min_index = i;	
			
			// 최솟값을 갖고있는 인덱스 찾기 
			for(int j = i + 1; j < size; j++) {
				if(a[j] < a[min_index]) {
					min_index = j;
				}
			}
			
			// i번째 값과 찾은 최솟값을 서로 교환 
			swap(a, min_index, i);
		}
	}
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
}