삽입 정렬

위키백과 ― 우리 모두의 백과사전.

삽입 정렬의 예.
삽입 정렬의 예.

삽입 정렬은 자료 리스트의 모든 요소를 하나씩 차례로 정렬된 리스트의 부분과 비교하여, 자신의 위치를 찾아 삽입하므로써 정렬을 완성하는 알고리즘이다. 리스트가 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

목차

[편집] 예제

다음의 주어진 리스트의 삽입정렬은 다음과같다.

31 25 12 22 11 //값 31은 나머지 자료값과 비교
11 25 12 22 31 //값 31은 최대값이므로 맨뒤에 위치
11 12 25 22 31 //다음값 25는 12보다 크므로 교환
11 12 22 25 31 //값 25는 22크고 31작으므로 값22와 교환


[편집] C++로 짠 삽입정렬

void insert(const Element e,Element *list,int i)
{
   while(e.getKey()<list[i].getKey())
   {
      list[i+1]=list[i]
      i--;
   }
   list[i+1]=e;
}

[편집] JAVA로 짠 삽입정렬

 

[편집] 복잡도

최악의 경우 i+1번의 비교를 하게되고 이때의 시간복잡도는  O(\sum_{n-1}^{i=1}{i+1})=O(n^2) 이 된다.