📌 삽입 정렬

• 삽입 정렬은 자신보다 앞의 원소가 큰지 작은지 비교를 해서 알맞은 위치를 찾아서 '삽입' 하는 정렬이다.
• 이때 자신보다 앞의 원소를 비교하므로 2번째 index부터 시작한다.
• 삽입 정렬은 앞에서부터 차례대로 정렬을 완성해나가는 알고리즘이다. 따라서 삽입 위치를 찾고자 하는 현재 원소(key 라고 하자)보다 앞의 원소(front_num 이라고 하자)의 값이 작은 경우, 현재 위치가 해당 key의 삽입 위치이므로 순회를 종료한다. (왜냐하면 front_num 앞은 이미 정렬이 완성되어 있는 상태이기 때문이다.)

---

📌 삽입 정렬 구현하기

• 삽입 정렬을 이해하기 위해 다음과 같이 정렬되지 않은 [5, 1, 4, 3, 2]를 정렬해보자.
• 정렬 과정은 아래 그림과 같다.

과정

• 삽입 위치를 찾고 싶은 원소는 data[index]이다. 각 index에 대하여 해당 data[index]의 삽입 위치를 찾기 까지의 과정을 1번의 턴이라고 정의하자.
• 각 턴의 index에 대하여 삽입 위치를 찾기 위해 해당 index보다 앞의 원소들이 큰 지 작은 지 비교해야 한다.
• 이때 앞의 원소들의 인덱스를 비교하기 위해 index2를 사용했다.
  • 단, index2의 범위는 (1 ~ index)이다. 왜냐하면 data[index2]는 삽입하고자 하는 원소로 사용할 것이고, data[index2 - 1]는 index의 앞의 원소로 사용할 것이기 때문이다.
• 따라서 data[index2 - 1]는 index의 앞 원소로, data[index2]는 index에 해당하는 원소로 사용한다.
• data[index2 - 1] > data[index2] 이면 앞 원소보다 현재 원소가 더 작은 경우이므로 두 원소의 자리를 바꾼다.
• 만약 data[index2 - 1] < data[index2]이면 순회를 종료한다. 현재 위치가 해당 data[index2] 즉, data[index]의 알맞은 삽입 위치이다.

---

문제 해결 요약

1. for index in range(len(data)) 으로 반복
2. for index2 in range(1 ~ index) 으로 반복
3. 삽입 위치를 찾고자 하는 원소는 data[index2], 비교 대상인 앞의 원소는 data[index2 - 1]
   - 삽입 위치를 찾고자 하는 원소를 data[index2]라고 설정했는 지 이해하기. 조금만 생각해보면 왜 항상 data[index2]에 data[index]의 값이 담겨 있는 지 이해할 수 있음. (swap하니까!)
   3-1. (내부 반복문 안에서) data[index2 - 1] < data[index2]이면 swap(data[index2 - 1], data[index])
   3-2. (내부 반복문 안에서) data[index2 - 1] < data[index2]가 아니면 더 이상 내부 반복문 순회 ❌

✅ Code

def insertion_sort(data):
    for index in range(len(data)):
        for index2 in range(index, 0, -1):  # index2는 (1 ~ index)까지 
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

---

📌 삽입 정렬 시간 복잡도

• 반복문이 두 개 $O(n^2)$

• 최악의 경우, $\frac { n * (n - 1)}{ 2 }$

• 완전 정렬이 되어 있는 상태라면 최선은 $O(n)$