[정렬] 삽입정렬 ( Insertion Sort )

void InsertionSort(vector<int>& v, int n) {
	int i, j,temp;
	for (i = 2;i < n;i++) { //v[0] = -1 더미값 세팅
		temp = v[i];
		j = i;
		while (v[j - 1] > temp) { //이전 값과 비교 후 크면 스왑
			swap(v[j], v[j - 1]);
			j--;
		}
	}
}

void insertionSort(vector<int>& v, int n) {
	int i, j;
	for (i = 1; i < n; i++) {
		for (j = i; j >0;j--) {
			if (v[j] < v[j - 1]) swap(v[j], v[j - 1]);
		}
	}
}

 

알고리즘

1. v[0] 에 더미값 세팅 

2. 삽입할 값 temp 에 저장

3. temp 값과 temp 이전 값들과 비교후 크면 스왑