Insertion Sort(삽입 정렬)

1번째 index부터 앞의 값들을 순차적으로 탐색하며 정렬

 

#include <stdio.h>
#include<stdlib.h>

template <typename T>
void insertionSort(T arr[], const int size) {
	for (int i = 1; i < size; i++) {
		T tmp = arr[i];
		int j;
		for (j = i - 1; j >= 0 && tmp < arr[j]; j--) {
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = tmp;
	}
}