삽입정렬의 개념 및 파이썬에서의 구현

삽입정렬은 기본적인 정렬 알고리듬 중 하나로, 검사하는 원소를 이 보다 큰 원소들의 앞 위치로 옮기는 것을 반복한다. 성능은 결국 (O(n^2))만큼의 나오지만 (실제로는 (n \times (n-1))번 비교한다. 대신에 원본이 정렬된 상태에 가까우면 가까울수록 삽입(결국은 배열내 원소의 위치 이동)이 적게 일어나므로 유리하게 동작할 수 있어서 평균적으로 버블정렬보다는 훨씬 빠르게 동작할 수 있다.

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

이렇게 검사하는 위치는 두번째, 세번째,… 마지막 원소에 이르는 식으로 이동한다.

알고리듬

알고리듬은 다음과 같이 동작한다. 먼저 배열이 다음과 같다고 가정한다.

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

두번째 원소부터 시작하여 앞쪽으로 비교한다 앞쪽 원소가 더 크면 이동할 일이 없지만, 앞쪽의 원소가 클 때 위치 이동이 필요하다. 3번 원소인 26을 보면,

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

앞에 위치한 45, 53이 더 크므로

[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]

이와 같은 방식으로 시작하는 위치를 3, 4번째 인덱스로 해서 앞쪽에 자신보다 큰 값이 있는 지를 비교한다.

[26][45][53][93][62][20][33][17]
             ~~ // 통과
[26][45][53][93][62][20][33][17]
            ^    ~~ // 이동
[26][45][53][62][93][20][33][17]
                 ~~ // 통과
[26][45][53][62][93][20][33][17]
^                    ~~ // 이동
[20][26][45][53][62][93][33][17]
        ^                ~~ // 이동
[20][26][33][45][53][62][93][17]
^                            ~~ // 이동
[17][20][26][33][45][53][62][93]
                             ~~ // 통과

그리고 비교 위치가 배열의 끝에 다다르면 이동이 끝났다.

삽입 정렬은 비교하고자 하는 인덱스로부터 왼쪽으로 이동하면서 자신이 찾아갈 자리를 찾기만 하면 되므로 비교의 횟수는 버블정렬에 비해 적지만, 한 번의 삽입이 일어나기 위해서는 여러 원소의 위치를 연속적으로 바꿔야 하는 작업이 필요하다. 따라서 가능하면 덜 뒤섞여있는 형태의 배열에서 좋은 성능을 낼 수 있다.

그럼에도 불구하고 위치이동을 통한 삽입을 구현하였으므로 big O 표기에 있어서 성능은 버블 정렬과 고만고만한 수준이 된다. (삽입 자체는 5번이지만, 이를 위한 대입 작업은 30회를 수행했다) 이 삽입정렬 자체의 평균적인 성능은 버블 정렬보다 좋다고 할 수는 있으나 이를 보다 개선하기 위해서는 쉘정렬이라는 알고리듬을 별도로 사용할 수 있다.

버블 정렬을 이용하는 경우 이 배열은 21번의 위치교환이 필요하고. 위치 교환은 swap으로 발생하기 때문에 회당 3번의 대입이 발생하여 총 63회의 대입이 발생한다. 결국 삽입정렬은 인접한 인덱스의 원소간의 스와핑을 한 번으로 줄이는 역할을 한다. (그래도 대입 연산은 1/2 수준으로만 발생했다.)

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentValue = alist[index]
        position = index
        while position > 0 and alist[position - 1] > currentValue:
            alist[position] = alist[position -1]
            position -= 1
        alist[position] = currentValue

파이썬에서 삽입 정렬의 성능을 향상하는 법

예를 들어 j 번째 원소가 i 번째 위치로 이동해야 하는 상황(이때, i < j 이다)을 생각해보자. j 번째 원소가 i 번째 위치로 이동하기 위해서는 i ~ j-1 의 위치의 원소들이 뒤에서부터 각각 한 칸씩 오른쪽으로 이동해야 한다. 따라서 대입 동작이 (j – i – 1)회 필요하다. 단, 이 때의 동작이 리스트 내의 부분열이므로, 이 동작은 리스트의 슬라이스 대입으로 치환할 수 있다.

currentValue = arr[j]
pos = j-1
while pos >= i:
    arr[pos+1] = arr[pos]
    pos -= 1
arr[pos] = currentValue

이 동작은 아래의 코드로 대치할 수 있다.

currentValue = arr[j]
arr[i+1:j+1] = arr[i:j]
arr[i] = currentValue

따라서 좀 더 pythonic 하게 다시 작성한 삽입 정렬 코드는 아래와 같다. 파이썬 런타임 범위에서 원소를 대치하는 횟수가 줄어들기 때문에1 성능은 위의 코드보다 조금 더 좋아진다.

def insertion_sort(aList):
    for (j, currentValue) in enumerate(range(1, len(aList))):
        i = j
        while i > 0 and aList[i] > currentValue:
            i -= 1
        aList[i+1:j+2] = aList[i:j+1]
        aList[i] = currentValue

  1. 파이썬에서 리스트 슬라이스를 대입하는 코드는 C레벨에서 동작하며, 해당 범위에 대해 루프를 돌면서 파이썬 레벨에서 원소를 일일이 업데이트하는 것보다 훨씬 빠르게 동작한다. 같은 이유로 에라토스테네스의 체 같은 것을 만들 때 이 문법을 활용하면 고성능의 코드를 얻을 수 있다.