Insertion Sort

접근

• 정렬 대상이 될 원소를 두 부분으로 나눈다.

  • 앞 부분은 ‘이미 정렬이 된 부분’
    • 정렬이 이 자체로 끝났다는 뜻이 아닌, 앞 부분에 있는 원소는 오름차순을 만족한다는 뜻
    • 아래의 사진에서 색칠 된 부분이 앞 부분을 의미함.
  • 뒷 부분은 ‘정렬할 부분’

• 매번 정렬할 부분의 가장 첫번째 원소를 정렬이 된 부분에 삽입(insertion)을 한다.

• 삽입은 정렬된 부분의 가장 큰 원소 (= 가장 오른쪽 원소)부터 오른쪽으로 비교해나가면서 진행한다.

정확성

• 이미 정렬된 부분은 항상 정렬이 되어 있다.
• 처음에는 정렬된 부분에 원소 1개 → 원소 1개는 그 자체로 정렬되어 있다.
• 매번, 정렬할 부분의 원소 1개를 이미 정렬된 부분으로 옮긴다.
  • 정렬할 부분의 원소는 처음 n-1개이다.
  • 매번 1개씩 감소해 최종적으로는 정렬된 부분에 n개, 정렬할 부분엔 0개가 되므로 최종적인 상태는 정렬된 상태일 것임.

구현

def insertion_sort(L):
    result = list(L)
    if len(result) == 1:
        return result
    sorted_idx = 0  # 0까지만 정렬이 됨
    for i in range(len(result)-1):
        sorted_idx += 1  # 정렬할 부분의 길이가 1씩 증가
        for x in range(sorted_idx, 0, -1):
            if result[x] < result[x-1]:
                result[x], result[x-1] = result[x-1], result[x]
            else:  # 오름차순으로 정렬이 되어있으니 break
                break
    return result

• Bubble Sort와 거의 유사하지만 삽입 정렬은 앞 부분은 정렬이 되어 있다고 가정하며 동작하기 때문에 조금 더 빠르다

시간 복잡도

• 가장 좋을 경우

  • 이미 오름차순으로 정렬이 되어있는 경우이다
  • 정렬된 부분에 원소를 넣을 때마다, 비교를 한 번만 하면 된다.
    • 총 $n -1번 = \theta(n)$

• 최악의 경우

  • 역순으로 정렬된 수들을 정렬할 때
  • 모든 경우(정렬된 부분에 원소를 넣는)에 비교를 최대로 해야한다.
    • 총 $1 + 2 + ...+(n-1) = \theta(n^2)$

• 평균 시간 복잡도

  • i개의 정렬된 부분에 i+1번째 원소를 삽입할 때
  • 삽입을 마치면 정렬된 부분에는 i+1개의 원소가 존재하고, 새로 들어온 원소는 이 중에서 1등부터 i+1등까지 가능하다
  • i+1등할 확률은 1/(i+1)이고, 비교는 1번 진행
  • i등할 확률은 1/(i+1)이고, 비교는 2번 진행
  • …
  • 2등할 확률은 1/(i+1)이고, 비교는 i번 진행
  • 1등할 확률은 1/(i+1)이고, 비교는 i번 진행
  • 이를 기댓값의 선형성에 따라 모두 곱하고 합하면…
  • 이런 i+1번째 원소는 n-1개가 있으니 …

• 포인트는 i+1번째 원소를 추가하는 행위를 n-1번 반복한다는 것에 있다.

• 그것들을 모두 곱해서 더하면 평균적인 시간 복잡도가 유도된다.