3. 삽입 정렬

< 삽입 정렬 >

 

■ 삽입 정렬 : 각 숫자를 적절한 위치에 삽입하는 방법

 

삽입 정렬은 기본적으로 '정렬이 되어 있다는 가정'을 한다는 점에서 특정한 경우에 따라서 굉장히 빠른 속도를 자랑한다. 

 

#include <stdio.h>
int main(void) {
	int i , j, temp; 
    
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    
    for(i = 0; i < 9; i++) {
		while( array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
    }
    
    for(i = 0; i < 10; i++) {
    	printf("%d\n", array[i]);
     }
    
    return 0;
}

 

10 + 9 + ... + 1

= O ( N * N )

= O ( N^2)

= 시간 복잡도

 

>> 선택 정렬, 버블 정렬, 삽입 정렬 셋 중 가장 효율적

 

>> 데이터가 이미 거의 정렬된 상태에서는 어떤 알고리즘보다도 빠르다.