삽입 정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
삽입 정렬의 예

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

Array prior to the insertion of x

각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다.

Array after the insertion of x

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

삽입 정렬의 예

예제[편집]

31 [25] 12 22 11   두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25> 31 [12] 22 11   세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12> 25 31 [22] 11   네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12 <22> 25 31 [11]   마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11> 12 22 25 31   종료.

소스 코드[편집]

JAVA[편집]

void insertionSort(int[] arr)
{
 
   for(int index = 1 ; index < arr.length ; index++){
 
      int temp = arr[index];
      int aux = index - 1;
 
      while( (aux >= 0) && ( arr[aux] > temp) ) {
 
         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}


 }

} </source>

C++[편집]

#include <iterator>
 
template<typename biIter>
void insertion_sort(biIter begin, biIter end)
{
    biIter bond = begin;
    for (++bond; bond!=end; ++bond) 
    {
      std::iterator_traits<biIter>::value_type key = *bond;
      biIter ins = bond;
      biIter pre = ins;
      for (--pre; ins != begin && *pre > key; *ins-- = *pre--;)
      *ins = key;
    }
}

Objective Caml(OCaml)[편집]

let rec isort = function
	| [] -> []
	| h::t -> insert h (isort t)
and insert a = function
	| [] -> [a]
	| h::t when a<h -> [a] @ (h::t)
	| h::t -> [h] @ (insert a t);;

복잡도[편집]

n개의 데이터가 있을 때, 최악의 경우는 \sum_{i=1}^{n-1}{i} = 1+2+3+4+\cdots + (n-1) = \frac{n(n-1)}{2}번의 비교를 하게 되므로, 시간복잡도는 O(n^2)이 된다.