Elementary Sorts(3) : Insertion Sort

Insertion sort demo

• 모든 값을 왼쪽에서부터 오른쪽으로 살펴보던 선택정렬과 달리,
  삽입 정렬은 i의 값은 왼쪽에서 오른쪽으로 이동하지만, j의 값은 오른쪽에서 왼쪽으로 이동합니다.
• j는 0부터 i-1까지의 값이 되는데, 리스트에서 i 번째 값보다 큰 값이 있다면 교환하는 작업을 반복적으로 수행합니다.

 

Insertion sort inner loop

n = len(a)
for i in range(n):
    for j in range(i-1,0,-1):
        if a[j] < a[j-1]:
            a[j],a[j-1] = a[j-1],a[j]
        else: break

• 삽입 정렬을 파이썬으로 구현한 것은 위와 같습니다.
  중간에 더 작은 값을 만나게 되어 정렬이 보장되는 경우 break를 통해 반복문을 탈출합니다.

 

Insertion sort: mathematical analysis

• 삽입 정렬은 1/4 N^2 번의 비교와 교환 명령을 수행합니다.
  둘을 합치면 1/2 N^2 번 명령이 수행되는 것이므로 선택 정렬에 비해 조금 더 효율적이라는 것을 알 수 있습니다.

 

Insertion sort: best and worst case

• 모든 원소들이 정렬된 최선의 경우, 실제 swap이 일어나지 않고 탐색도 원소의 개수만큼만 수행됩니다.(정확히는 N-1번)
• 하지만 내림 차순으로 정렬된 최악의 경우, 탐색도 교환도 1/2 N^2번 일어나므로 오히려 선택 정렬보다도 비효율적입니다.

 

Insertion sort: best and worst case

• 만약 inversion의 수가 선형(특정 정수 x n 보다 작은 경우)이라면, 배열이 부분적으로 정렬되었다고 볼 수 있습니다.
  왜냐하면 교환 횟수는 inversion 횟수와 동일하기 때문입니다.
• 부분적으로 정렬된 배열에 대해 삽입 정렬이 굉장히 효율적이라는 것을 설명하는 부분입니다.

 

 

출처: Coursera, Algorithms, Part 1, Princeton University