삽입 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{알고리즘 정보
|class=[[정렬 알고리즘]]
|image=[[파일:Insertion_sort.gif|300px]]
|caption=삽입 정렬의 애니메이션 GIF<ref>{{웹 인용|last=Simpsons |first=Unknown |title=Visualising Sorting Algorithms |url=https://upload.wikimedia.org/wikipedia/commons/4/42/Insertion_sort.gif |date=28 November 2011|accessdate=16 November 2017|mode=cs2}}</ref>
|data=[[배열]]
|time=О(''n''<sup>2</sup>) 비교 및 교환
|best-time=O(''n'') 비교, O(''1'') 교환
|average-time=О(''n''<sup>2</sup>) 비교 및 교환
|space=О(''n'') 전체, O(''1'') 보조
|optimal=아니오
}}
[[파일:Insertion sort animation.gif|프레임|오른쪽|삽입 정렬의 예]]

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

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

[[파일:insertionsort-before.png|Array prior to the insertion of x]]

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

[[파일:insertionsort-after.png|Array after the insertion of x]]

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

[[선택 정렬]]이나 [[거품 정렬]]과 같은 [[점근 표기법|O]](n<sup>2</sup>) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

[[파일:Insertion sort 001.PNG|프레임|오른쪽|삽입 정렬의 예]]
== 예제 ==
{|align="center"
|-
|align="center"|31||align="center"|25||align="center"|12||align="center"|22||align="center"|11||
|||처음 상태.
|-
|align="center"|31||align="center"|[25]||align="center"|12||align="center"|22||align="center"|11||
|&nbsp;||두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
|-
|align="center"|<25>||align="center"|31||align="center"|[12]||align="center"|22||align="center"|11||
|&nbsp;||세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
|-
|align="center"|<12>||align="center"|25||align="center"|31||align="center"|[22]||align="center"|11||
|&nbsp;||네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
|-
|align="center"|12||align="center"|<22>||align="center"|25||align="center"|31||align="center"|[11]||
|&nbsp;||마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
|-
|<11>
|12
|22
|25
|31
|
|&nbsp;
|종료.
|}

== 소스 코드 ==
=== [[자바 (프로그래밍 언어)|JAVA]] ===
<syntaxhighlight lang="javascript+erb">
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;
   }
}
</syntaxhighlight>

=== [[C (프로그래밍 언어)|C]] ===
<syntaxhighlight lang="cpp">
void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ){
        data[j+1] = data[j];
    }
    data[j+1] = remember;
  }
}
</syntaxhighlight>

아래는 정렬되는 자료가 단순 데이터일 경우에 <code>memcpy()</code>를 이용하여 자료를 밀어내는 예제이다.
<code>memcpy()</code>는 자료를 당겨야하므로 비교를 역순으로 수행한다.
위의 코드보다 25~30%가량 빠르게 처리된다.
<syntaxhighlight lang="cpp">
void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  i = n-1;
  while ( i-- > 0 )
  {
    remember = data[(j=i)];
    while ( ++j < n && remember > data[j] );

    if ( --j == i ) continue;
    memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );
    data[j] = remember;
  }
}
</syntaxhighlight>

=== [[C++]] ===
<syntaxhighlight lang="cpp">
#include <iterator>

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

=== [[Objective Caml]]([[OCaml]]) ===
<syntaxhighlight lang="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);;
</syntaxhighlight>

=== [[파이썬]] ===
<syntaxhighlight lang="python">
def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x
</syntaxhighlight>

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

== 각주 ==
{{각주}}

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]
[[분류:안정 정렬]]
[[분류:비교 정렬]]
[[분류:온라인 정렬]]