정렬 (3) - 삽입 정렬 (Insertion Sort)

1. 알고리즘 개요

• 외워야 하는 것 : 정렬되지 않은 원소를 정렬된 리스트에 적합한 위치를 찾아 삽입하는 것 
• 시간복잡도 : $O(n^2)$
• 특징 : 거의 정렬이 되어있는 문제에는 빠르다 (inner loop가 줄어든다)

 

[그림] 삽입정렬 애니메이션

 

2. 소스코드

void insertion_sort(int *arr, int size){
	
	for(int i = 1 ; i < size ; i ++){
		int curr = arr[i];
		int j = i - 1;
        // 아래에서 j 써야해서 여기에서 선언
		
		for(; curr < arr[j] && j >= 0; j--){
        //arr[j]가 curr보다 크면 점점 앞으로 감
        
			arr[j + 1] = arr[j];
		}
        
		arr[j + 1] = curr;	
	}
}

 

3. Reference