[알고리즘]삽입정렬(InsertionSort)

삽입정렬

• 배열의 모든 요소를 앞에서부터 차례대로 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘

코드

구현(C++)

void InsertionSort(int list[], int n) {
	int i, j, key;

	for (i = 1; i < n; i++) {
		key = list[i];

		for (j = i - 1; j >= 0 && list[j] > key; j--) {
			list[j + 1] = list[j]; 
		}

		list[j + 1] = key;
	}
}