선택 정렬(Selection sort)

1. 주어진 리스트에서 최솟값을 찾는다.

2. 최솟값을 맨 앞 자리의 값과 교환한다.

3. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다. 

자바로 구현한 코드는 다음과 같다.

static void selection_sort(int[] arr) {
	for (int i = 0; i < arr.length - 1; i++) {
    	int minIndex = i;
    
    	for (int j = (i+1); j < arr.length; j++) {
        
        	if (arr[j] < arr[minIndex]) {
            	minIndex = j;
            }
        }
    
    	swap(arr, i, minIndex);
    }

}

static void swap(int[] arr, int i, int j) {
	int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

시간 복잡도는 O(N²) 이다.

---

참조한 책 및 사이트

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC