Insertion Sort (삽입정렬)

https://velog.io/@yc1303

 

두번째 인덱스값(temp)부터 시작하여 왼쪽 범위를 탐색하여 정렬한다.

왼쪽 범위를 탐색하여 temp값을 자신의 위치에 정렬한다.

시간 복잡도: 왼쪽 부분에 데이터가 하나 정렬될 때마다 (n-1)+(n-2)+....

-> (n-1)+(n-2)+(n-3)+.....1 = n*(n-1)/2 -> O(n^2)

 

Code

#include <iostream>
using namespace std;

#define size 10

int main() {

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

	cout << "정렬 전 : ";
	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";

	for (int i = 1; i < size; i++) {
		temp = arr[i];
		
		for (j = i - 1; j >= 0; j--) {
			if (arr[j] >= temp)
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j+1] = temp;
	}
	cout << "\n정렬 후 : ";

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