삽입 정렬(Insertion Sort)

https://thumbs.gfycat.com/DenseBaggyIbis-size_restricted.gif

 

위 그림처럼 하나 key값이 파고들면서 제위치를 찾아간다고 생각하면 이해하기 쉽다

맨 첫번째 원소는 정렬 되어 있다고 가정한 후 두번째 원소부터 비교를 시작하는데 인덱스를 줄여나가면서 앞 원소가 더 큰값이라면 위치를 바꾸는 것을 반복

한 사이클이 돌 때마다 위 그림상 노란색으로 표시 되는 부분이 정렬 순서거 확정된다.

최악의 경우 시간복잡도는 O(N^2)이다.

ex) 4 3 2 1을 삽입정렬한다고 가정하면 두번째 원소부터 

4와 비교 -> 1번 연산

3,4, 비교 -> 2번연산

2,3,4,비교 -> 3번연산

즉, n(n-1)/2 와 같다.

 

 

#include <iostream>

using namespace std;

int main() {

	int arr[] = { 6,9,8,1,3,4,2,5,7 };
	int arrSize = sizeof(arr) / sizeof(int);
	int tmp;
	for (int i = 1; i < arrSize; i++) {
		int key = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
		
	}

	for (int i = 0; i < arrSize; i++) {
		cout << arr[i] << " ";
	}


}