정렬 (2) - 선택 정렬 (Selection Sort)

1. 알고리즘 개요

• 외워야하는 것 : 최소값의 인덱스(min)를 찾아서 정렬되지 않은 부분의 제일 앞으로 보내기
• 시간 복잡도 : $O(n^2)$
• 특징 : 교환회수가 적어서 큰 레코드를 다룰 때 적합

 

[그림] 선택정렬 애니메이션

 

2. 소스코드

void selection_sort(int *arr, int size){
	
	for(int i = 0 ; i < size ; i++){
    	int min = i;
    	
        for(int j = i; j < size ; j++){
        // 이전에 정렬된 부분 제외하고 i부터 끝까지
        
            if(arr[j] < arr[min]){
            // 최소값을 찾았을 때
            
            	min = j;
            }
        }
        
        swap(&arr[min], &arr[i]);
    }
}

 

3. Reference