[Sort]Insertion Sort

- 매 반복마다 뒤쪽의 정렬되지 않은 요소들의 목록에서 요소를 삭제하고 삭제한 요소를 앞쪽의 이미 정렬된 목록 내 알맞은 자리에 삽입.

 

- 입력 데이터에서 삭제될 요소는 정렬되지 않은 목록에서 무작위로 선택(보통 앞에서 차례대로)

 

- 0번과 1번 인덱스는 정렬이 되어 있다고 가정(반복되면서 알아서 정렬됨)

 

- 시간 복잡도

   Worst: O(n^2)

   Best: O(n)

   Average: O(n^2)

 

- 공간 복잡도: O(1)

 

- 삽입 정렬은 미리 데이터가 어느 정도 정렬 되어 있거나 입력 데이터가 적을 경우 사용. 

   --> 병합 정렬 or 퀵 정렬과 같은 분할 정복 알고리즘의 base case로 사용되기도 함

 

void insertion_sort(int arr[], int size_arr) {

	for (int i = 2; i < size_arr; i++) {
		int v = arr[i];
		int j = i;
		while (arr[j - 1] > v && j >= 1) {
			arr[j] = arr[j - 1];
			j--;
		}
		arr[j] = v;
		
	}
	print_arr(arr, size_arr);
}