삽입정렬

Updated:

개념

  • 손 안의 카드를 정렬하는 방법과 유사합니다.
    • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입합니다.
    • 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬됩니다.
  • 자료 배열의 모든 요소를 앞에서부터 1칸씩 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.
  • 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣습니다.


특징

  • 선택/거품 정렬은 패스가 거듭될 수록 탐색 범위가 줄어드는 반면에, 삽입 정렬은 오히려 점점 정렬 범위가 넓어집니다.
  • 큰 크림에서 보았을 때 바깥 쪽 루프는 순방향, 안 쪽 루프는 역방향으로 진행하고 있습니다.


복잡도 분석

  • 최악: O(n^2) & 최선 (이미 정렬되어 있는 경우): O(n)
  • 삽입 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가집니다.
  • 시간 복잡도는 우선 루프문을 통해 정렬 범위를 2개로 시작해서 전체로 확장해야 하기 때문에 기본적으로 O(N)을 시간을 소모하며, 각 패스에서는 정렬 범위에 새롭게 추가된 값과 기존 값들의 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요하게 됩니다. 따라서 삽입 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
  • 아래에서 다룰 최적화를 통해서 부분적으로 정렬된 배열에 대해서 성능을 대폭 개선할 수 있으며, 특히 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있습니다.


구현

  • 2개의 반복문이 필요합니다.
  • 내부 반복문에서는 정렬 범위에 새롭게 추가된 값과 기존 값들을 뒤에서부터 계속해서 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 swap합니다.
  • 외부 반복문에서는 정렬 범위를 2에서 N으로 확대해 나갑니다.
def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]


최적화시킨 코드

  • 이미 기존에 있던 값들이 정렬되어 있을 때를 활용해 불필요한 비교 작업 제거.
def insertion_sort(arr):
    for end in range(1, len(arr)):
        to_insert = arr[end]
        i = end
        while i > 0 and arr[i - 1] > to_insert:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = to_insert

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/9eede9fa-3477-443c-be58-0841ee75138e/Untitled.png

1회전: 두 번째 자료인 5를 Key로 해서 그 이전의 자료들과 비교한다.

  • Key 값 5와 첫 번째 자료인 8을 비교한다. 8이 5보다 크므로 8을 5자리에 넣고 Key 값 5를 8의 자리인 첫 번째에 기억시킨다.

2회전: 세 번째 자료인 6을 Key 값으로 해서 그 이전의 자료들과 비교한다.

  • Key 값 6과 두 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 6이 있던 세 번째 자리에 기억시킨다.
  • Key 값 6과 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 작으므로 Key 값 6을 두 번째 자리에 기억시킨다.

3회전: 네 번째 자료인 2를 Key 값으로 해서 그 이전의 자료들과 비교한다.

  • Key 값 2와 세 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 2가 있던 네 번째 자리에 기억시킨다.
  • Key 값 2와 두 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 세 번째 자리에 기억시킨다.
  • Key 값 2와 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 두 번째 자리에 넣고 그 자리에 Key 값 2를 기억시킨다.

4회전: 다섯 번째 자료인 4를 Key 값으로 해서 그 이전의 자료들과 비교한다.

  • Key 값 4와 네 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 다섯 번째 자리에 기억시킨다.
  • Key 값 4와 세 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 네 번째 자리에 기억시킨다.
  • Key 값 4와 두 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 세 번째 자리에 기억시킨다.
  • Key 값 4와 첫 번째 자료인 2를 비교한다. 2가 Key 값보다 작으므로 4를 두 번째 자리에 기억시킨다.


참고자료

  • https://blog.naver.com/ndb796/221226806398
  • https://www.zerocho.com/category/Algorithm/post/57e39fca76a7850015e6944a
  • https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
  • https://www.daleseo.com/sort-insertion/

Leave a comment