3. 삽입 정렬

삽입 정렬

삽입 정렬은 각 숫자들을 적절한 위치에 삽입하는 알고리즘입니다. 여기서 가장 KEY포인트는 필요할 때만 위치 변경이 이루어진다는 것입니다. 오름 차순 기준으로 자신보다 작은 원소를 만났을 때만 위치 변경이 이루어집니다.(비교를 통해 필요할 때만 자신의 위치를 찾아서 들어가므로 그 과정들이 다 정렬 상태입니다.) 따라서 실제 시간 복잡도는 O(n²)이지만(반복문이 2번 돌기에...) 데이터가 이미 어느정도 정렬되어 있을 경우 매우 빠른 알고리즘입니다.

#include <iostream>

using namespace std;

int main() {
	int i, j, temp;
	int array[10] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 1 }; // 위 처럼 거의 정렬된 상태에서 다른 알고리즘 보다 더욱 효율적 -> 이 경우 삽입정렬에서는 거의 연산을 안하기 때문!

	for (i = 0; i < 9; i++) {
		j = i;
		while (j >= 0 && array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}

	for (i = 0; i < 10; i++) {
		cout << array[i] << " ";
	}

	return 0;
}