삽입 정렬이란 두 번째 원소부터 그 앞의 원소들과 차례로 비교해가며 위치를 옮겨가는 정렬이다. 삽입 정렬의 특징 하나의 배열 내에서 위치변경만 일어나므로 공간복잡도는 O(1) in-place 정렬이다시간복잡도는 평균 O(n^2) 최악 O(n^2)키 값이 같을 경우에도 정렬 후에 순서가 유지되므로 stable정렬이다선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다 구현 (C++) #include using namespace std;#define listLength 5void Insertion_sort(int list[]){ int key; for (int i = 1; i = 0; j--) { if(list[j] > key) // 위치 변경 ..
