알고리즘_4_삽입 정렬

Aug 8, 2021 » writing

K 실전 알고리즘 강좌(Algorithm Programming Tutorial) 동빈나 님 수업을 참고하여 작성하였습니다

4_삽입 정렬

정의

삽입 정렬

1. 정렬 (Sort)
   3) 삽입 정렬 (Insertion Sort)
        : 각 숫자를 적절한 위치에 삽입하는 방법
		: 필요할 때만 위치를 바꾼다
		: 정렬되어 있다고 가정하면 굉장히 빠르다
		: 반복문이 두번 들어가 있다

각 숫자를 적절한 위치에 삽입하면 어떨까?

#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 ++) {
		j = i;
		while (j >= 0 && 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 " , array[i]);
	}
	return 0;
}
// 1 2 3 4 5 6 7 8 9 10

삽입 정렬의 시간 복잡도는 N^2