삽입 정렬(insertion sort) 란?

삽입정렬의 원리 

삽입 정렬(insertion sort)은 손안의 카드를 정렬하는 방법과 유사하다. 우리는 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 

 

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

 

삽입 정렬은 처음에 2번 째 위치의 값을 key로 정해서 시작한다. key 값을 자신의 왼쪽에 놓인 것들과 하나씩 비교하면서 자신의 위치를 찾으면 그 자리의 있는 것과 자리를 바꾸게 된다. 자바로 삽입 정렬을 구현해보자.

 

 

 

 

삽입 정렬의 복잡도 분석

삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 최선의 경우는 먼저 입력자료가 이미 정렬되어 있는 경우는 가장 빠르다. 최악의 경우는 입력 자료가 역순일 경우이다. 

 

 

최선의 경우  

삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교횟수는 n-1번, 총 이동횟수는 2(n-1)번이 되어 알고리즘 시간 복잡도는 O(n)이다. (최선의 경우이기 때문에 그렇다)

 

 

최악의 경우

각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동하여야 한다. 따라서 외부 루프안의 각 반복마다 i번의 비교가 수행되므로 총 비교횟수는 다음과 같다.

 

1 + 2 + ... + (n-1) = n(n-1)/2 = O(n*n) 

 

역순이라고 생각하면 정렬을 하는 과정에서 계속 자신의 위치보다 하나 앞에 있는 것과 비교1번, 이동1번 씩을 수행해서 자신의 위치 까지 와야한다. (그것이 i번이다)

 

총 이동횟수는 외부 루프의 각 단계마다 i+2번의 이동이 이루어지므로 다음과 같다. 

 

i번의 경우는 위의 비교처럼 n-1번 반복문을 수행하면 O(n*n)이 되고, +2번의 경우는 2(n-1)을 해서 두개를 더하면 된다.

시그마의 경우를 생각하자. 따라서 O(n*n)이다.  (n(n-1)/2 + 2(n-1) = (n*n + 3n -4)/2) 가 정확하다. 

 

 

 

삽입 정렬의 장단점 

• 장점

  • 안정한 정렬 방법으로서 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하다.
  • 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

 

• 단점

  • 레코드의 양이 많고 레코드 크기가 클 경우에 적합하지 않다.
  • 비교적 많은 레코드들의 이동을 포함한다.

 

 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

 

평균적인 상황에서 정렬의 속도가 빠른 것은 아니지만, 구현이 쉽고 어느정도 정렬이 되어 있는 상태에서는 아주 적합한 정렬이라고 생각한다.