삽입 정

 

다음 숫자들을 오름차순 정렬하시오

> 1 10 5 8 7 6 4 3 2 9

 

삽입 정렬

필요한 경우에만 위치를 바꾸어 정렬하는 삽입 정렬에 대해 알아볼 것이다. 비교적 느리지만 조금은 복잡한 구조이다.

 

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int j,temp;
	int arr[10] = {1,10,5,8,7,6,4,3,2,9};
	for(int i=0; i<9; i++){
		j = i;
		while(arr[j]>arr[j+1]){
			temp = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = temp;
			j--;
		}
	}
	for(int i=0; i<10; i++)
		cout << arr[i] << ' ';
	return 0;
}

 

시간복잡도

계산되는 범위가 10~1까지 줄어드는 것을 보아

선택, 버블 정렬과 같은 원리로 시간복잡도가 성립된다는 것을

알 수 있지만 연산은 삽입 정렬이 더 빠름

 

만약 거의 정렬된 상태라면 삽입 정렬이 어떤 알고리즘보다 빠르다고 할 수 있다.