삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

0. 삽입 정렬(Insertion sort)이란?

배열(array) / 리스트(list)의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열/리스트 부분과 비교하여, 위치를 찾아 삽입하여 정렬하는 방법

1. 삽입 정렬(Insertion Sort) 알고리즘 예제

[5, 1, 3, 7, 2, 9]의 배열

• 1회차
  배열에서 최솟값인 1을 찾아서 앞으로 이동합니다.

• 2회차
  1을 제외한 최솟값이 3을 찾아서 두번째 자리로 이동합니다.

• 3회차
  7은 이미 올바른 배열의 자리에 위치하므로 건너뜁니다.
  ...

• 최종
  1 2 3 5 7 9로 정렬을 완성

---

# Insertion Sort
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]
    return arr

# Insertion Sort - pseudo code
InsertionSort(A,n)
    for j ← 2 to n
        do key ← A[j]
            i ← j-1
            while i > 0 and A[i] > key
                do A[i+1] ← A[i]
                    i ← i-1
            A[i+1] ← key

2. 삽입 정렬(insertion sort)의 특징

• 장점
  • 자료 이동 횟수가 미리 결정된다.
• 단점
  • 안정성을 만족하지 않는다.
  • 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다.

---

3. 삽입 정렬(insertion sort)의 시간복잡도

• 비교 횟수

  • 두 번의 for 루프 실행 횟수
  • 외부 루프: (n-1)
  • 내부 루프: 최솟값 찾기

• 교환 횟수

  • 외부 루프와 실행 횟수가 동일하다. 즉, 상수 시간 작업.
  • 한 번 교환을 위해서 3번의 이동이 필요하다. 즉, 3(n-1)번

• T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n²)

References

Blog