3) 알고리즘 : 정렬 - 삽입정렬(Insertion Sort)

삽입정렬

 

- 적절한 위치에 삽입 하는 것

- 처음부터 왼쪽에 있는 원소와 비교해서 해당 원소가 비교값보다 작다면 왼쪽으로 이동하는 식으로

더 큰 수를 만날때까지 반복해준다.

- 항상 왼쪽에 있는 것은 정렬되어 있다고 가정되어 있음. 즉, 멈출 코드를 알고 있다는 것. (왼쪽의 원소값보다 해당값이 크면 멈추면 된다.)

- 시간 복잡도(Big O) : 10 + 9 + 8 + 7 ... + 1 

=> O(N^2)

- Big O는 선택/버블과 같지만 실제로는 선택/버블/삽입 중에서는 삽입이 제일 연산이 적다.

- 거의 정렬된 상태의 정렬을 삽입 정렬로 한다. => 삽입 정렬이 굉장히 빨라짐

 

 

// 삽입정렬 insertion sort

#include <iostream>
using namespace std;

int main(void) {

	int i, j, temp;
	int array[10] = { 1, 10, 5, 8, 7, 6, 4 ,3, 2, 9 };

	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;
}