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

삽입 정렬

• 특징
  • 하나씩 삽입하며 정렬한다.
  • k번째 자료에 대해 생각할 때, 앞의 k-1개 자료는 이미 정렬되어 있다.
• 복잡도분석
  • K번째 자료의 비교 회수
    • 최상 1회, 최악 (k-1)회, 평균 (k/2)
  • 전체 : 최상 (n-1), 최악 1+2+...+(n-1)=O(n2)
• 장단점
  • (+) 순서가 틀린 자료가 적을 때 (즉, 위에서 m이 작을 때)
  • (+) 20-25개 이하 정렬에 효과적
  • (-) 이동량 증가 (앞서 이동한 자료를 재이동) -> 리스트구조, 선택 정렬이 더 효과적

 

void insertion_sort(data A[], int n) {
int i, j;
data temp;
    for(i = 2; i <= n; i++) 
    {
    	temp = A[i];
        j = i;
        while(j > 1 && A[j-1] > temp) 
        {
        	A[j] = A[j-1];
            j--; 
        }
        A[j] = temp; 
	}
}

 

•  원소비교회수
  • 최상의 경우, n-1 = O(n)
  • 최악의 경우, 1+2+...+(n-1)=n(n-1)/2=O(n2)
  • 평균의 경우, O(n2) or O((m+1)n) 
• 원소이동회수 분석
  • 최악의 경우, n(n-1)/2+2(n-1)=O(n2) 

 

 

삽입 정렬 예시

#include <iostream>
using namespace std;

const int SIZE = 15;
int L[SIZE] = { 10, 4, 7, 1, -2, 12, 28, 66, 9, 3, 5, 7, 6, 21, 11 };


void print_data()
{
	for (int i = 0; i < SIZE; i++)
		cout << " " << L[i] << " ";
	cout << endl;
}

void insertion_sort()
{
	int i, j;
	int temp;
		
		for (i = 1; i < SIZE; i++)
		{
			temp = L[i];
			int j = i;
			while (j>0 && L[j-1]>temp)
			{
				L[j] = L[j - 1];
				j--;
			}
			L[j] = temp;
	}
	
}

void main()
{
	cout << "Input Data : ";
	print_data();

	insertion_sort();

	cout << "\n\nSorted Data : ";
	print_data();

}