[정렬 알고리즘] 삽입 정렬

🏆 목차.

1. 삽입정렬이란?
2. 삽입정렬 코드
3. 결론

 

🛒 삽입정렬이란?

 

삽입정렬은 선택정렬과 버블정렬보다는 효율적인 정렬 알고리즘입니다.

비교적으로 효율적인 이유는 삽입정렬은 이미 정렬된 상태에 한해서 정말 빠르다는 특징을 가지고 있기 때문입니다.

그림으로 설명하자면 다음과 같습니다.

 

삽입정렬 그림설명

 

그림과 같이 삽입정렬은 정렬하려는 원소를 앞에 있는 원소들과 비교하여 적합한 위치에 삽입하는 알고리즘입니다.

기존 선택정렬과 버블정렬의 경우 이미 정렬이 된 원소들과도 무조건적으로 비교를 하는데 반해, 삽입정렬은 이미 정렬된 부분과 새로운 원소만을 비교하기 때문에 효율적이라고 할 수 있습니다.

 

🎨 삽입정렬 코드

 

#include <iostream>

using namespace std;


int main() {
	
	int arr[10] = {4,5,3,7,8,1,9,2,6,10};
	int j;
	int temp;
	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]<<" ";
	}
}

 

위 코드의 핵심은 while 반복문을 통해 현재 원소가 뒤에 원소보다 크다면 서로 교체하고 j를 1 감소시키는 것입니다.

해당 코드를 통해 현재 원소가 크다면 뒤에 원소와 교체를 하고 다시 검사를 반복하게 됩니다,

반대로 현재 원소가 작다면 검사할 필요가 없기 때문에 반복을 진행하지 않습니다.

 

🎯 결론

 

기본적으로 삽입정렬은 O(n^2)의 시간복잡도를 가지고 있지만, 대부분의 원소가 이미 정렬이 되어있는 상태라면 즉, 최선의 경우 O(n)의 성능을 보입니다.

이 경우 퀵정렬과 다른 정렬들에 비해서 가장 빠른 속도를 가지고 있습니다.

하지만 큰 데이터를 정렬해야 하는 경우에는 그렇게 좋은 정렬 알고리즘은 아닙니다.