콘텐츠로 건너뛰기
Home » 삽입정렬

삽입정렬

삽입정렬(insertion sort)은 기본적인 제자리 정렬 알고리듬 중 하나로, 배열 내의 어떤 위치의 원소를 해당 배열의 가능한 가장 왼쪽 자리에 ‘삽입’하는 동작을 통해 정렬을 수행한다. 삽입 정렬의 이론적인 성능은 O_{(n^2)}이지만, 데이터가 정렬된 상태에 가깝다면 삽입 동작이 그 만큼 적게 일어나므로 더 빨라질 수 있다. 현실 세계의 데이터는 완전히 랜덤하기보다는 약간은 정렬된 경향을 가지므로 같은 O_{(n^2)}인 버블정렬 알고리듬보다는 더 빠르게 동작하는 것으로 알려져 있다.

알고리듬

삽입 정렬의 알고리듬 자체는 기본적으로 두 번째부터의 각 원소에 대해서 해당 원소보다 앞에 있는 원소들을 차례로 그 값과 비교해 나가서, 현재 원소가 이동할 수 있는 가장 왼쪽 끝으로 이동시키는 것이다. 그 과정에서 이동해야 하는 구간 사이의 원소들은 모두 오른쪽으로 한칸씩 이동해 나간다.

이렇게 검사하는 위치는 두번째, 세번째,… 마지막 원소에 이르는 식으로 이동한다. 먼저 배열이 다음과 같다고 가정한다.

[45][53][26][93][62][20][33][17]

두번째 원소 53부터 시작하여 앞쪽으로 비교한다. 53의 경우 왼쪽에 43이 더 작은 값이므로 이동할 곳이 없다. 세 번째 원소인 26의 경우를 보자.

[45][53][26][93][62][20][33][17]
         ~~

26 앞에 위치한 53이 더 크다. 따라서 53을 일단 뒤로 민다. 두 번째 위치에서 다시 왼쪽과 비교했을 때 45라는 큰 값이 또 있으므로 45도 뒤로 민다. 그리고 45 자리에 26을 넣는다. 이 동작은 결국, 45, 53을 뒤로 밀고 그 앞에 26을 끼워넣은 동작이다. 

[45][53][  ][93][62][20][33][17]
     --> 26
# 53을 오른쪽으로 이동
[45][  ][53][93][62][20][33][17]
 --> 26
# 45도 오른쪽으로 이동
 [  ][45][53][93][62][20][33][17]
  26
# 최종적으로 26이 비어있는 0번 인덱스로 이동
[26][45][53][93][62][20][33][17]

이와 같은 방식으로 시작하는 4번째, 5번째,… 이렇게 늘려나가면서 마지막 원소까지 이 동작을 반복하면 모든 자리에 있던 값들이 자신보다 큰 수들의 앞으로 옮겨가면서 정렬된 상태가 완성된다.

삽입 정렬에서 각 원소가 자신의 자리를 찾는 과정을 보면 이미 정렬되어 있는 부분이 많을 수록 원소의 이동이 (왼쪽의 원소를 뒤로 밀어내는) 줄어들게 되는 것을 알 수 있다. 다만 삽입하는 횟수가 적더라도, 삽입을 위해서 큰 원소를 뒤로 밀어내는 과정이 많이 발생하기 때문에 그렇게 효율이 좋은 알고리듬은 아니다. 대신 ‘정렬된 상태에 가까울수록 효율이 좋다’는 특성 때문에 다른 알고리듬과 결합하여 많이 쓰인다. Shell 정렬이 그 예.

이 알고리듬을 그대로 코드로 옮기면 다음과 같다. 

from typing import List, TypeVar
T = TypeVar('T')
def insertion_sort_a(xs: List[T]):
  # 두 번재 인덱스부터 반복
  for i in range(1, len(xs)):
    val, j = xs[i], i
    # 왼쪽으로가면서 같거나 큰 원소를 오른쪽으로 밀어냄
    # 더 작은 원소가 발견되면 멈춤
    while j > 0 and xs[j - 1] > val:
        xs[j] = xs[j - 1]
        j-= 1
    # 처음값을 빈 자리에 삽입
    xs[j] = val

삽입정렬은 최악의 경우 O_{(n^2)}의 성능을 보여주는데, 자료가 정렬된 상태에 가깝다면 효율이 좋다고 했다. 이는 ‘작은 값이 왼쪽에 있을수록’ 자리 바꿈이 일어나는 횟수가 적어지기 때문이다. 즉 각 원소가 먼거리로 땡겨져야 한다면 그 거리 사이의 모든 원소들이 한 칸씩 움직이는 동작이 먼저 필요하기 때문이다.

이 때, 삽입할 위치부터 원래 위치사이의 옮겨지는 값들은 모두 연속해 있는 데이터들이다. 따라서 while 루프를 따라 움직이면서 매번 원소를 값을 옮기지 않고, 삽입 위치만 체크한 후 슬라이스를 사용해서 한 번에 옮긴다면 성능을 더 높일 수 있다.

이 아이디어를 적용해서 코드를 다시 쓰면 아래와 같다.

def insertion_sort_v(xs: List[T]):
  for i in range(1, len(xs)):
    val, j = xs[i], i
    while j > 0 and xs[j - 1] > val:
        j-= 1
    if j < i:
      xs[j+1:i+1] = xs[j:i]
      xs[j] = val

이 코드는 각 원소가 이동할 곳을 찾을 때, 먼저 찾고 이동할 필요가 있을 때에 삽입의 준비동작을 슬라이드 대입으로 가능한 빠르게 처리한다. 아래는 1~200,000 사이의 정수 4,000개 배열에 대해서 두 코드의 성능을 비교한 것이다. 여기서는 조금 차이가 나는 것처럼 보이지만 상황에 따라서는 두 코드가 보이는 성능차이가 크게 다르지 않을 수 있다.

%%timeit
xs = ns[:]
insert_sort_a(xs)
# 1.16 s ± 2.16 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%%timeit
ys = ns[:]
insert_sort_v(ys)
# 836 ms ± 3.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
태그: