[누구나 자료구조 알고리즘] Python 삽입정렬

💡 Goal
- 삽입정렬 알고리즘을 이해한다.
- 삽입정렬 알고리즘을 파이썬으로 구현한다.
- 삽입정렬 알고리즘 특징을 2가지 이상 말하기.

개념

---

• 데이터를 앞에서 하나씩 확인 후 특정 조건에 부합하는 위치(좌 or 우)에 삽입
  • 왼쪽은 이미 정렬되어 있는 가정으로 접근
• 선택정렬에 비해 실행시간 측면으로 조금 효율적
• 처음 key값은 두번째(index 1)부터 시작
• 비교, 시프트(이동), 삽입등이 사용되는 알고리즘

순서(오름차순 기준)

---

1. 1번 인덱스부터 시작하는 반복문을 만든다.
2. 임시로 1번 인덱스값과 데이터를 가지고 ← 방향으로 반복 비교한다.
   1. 왼쪽은 이미 정렬되어 있다는 가정
3. 왼쪽 값이 크다면 큰 값을 현재 position으로 변경해주고 position을 -1 해준다. (왼쪽 순회)
4. 2,3단계가 끝나면 현재 position에 임시 데이터 값을 저장한다.

특징

---

장점

• 알고리즘 코드가 간단해 레코드의 수가 적을때 사용
• 레코드가 거의 정렬되어 있을때 효율적

단점

• 많은 데이터의 이동 발생
• 데이터가 많고 크기가 클수록 효율성 떨어짐

코드

---

# 1. 2중 for문으로 반복
# 2. i를 내부 for문의 j로 변수 주고 -1씩 반복 (0,1)(1,2) 비교하기 위함
# 3. 우측으로 이동할 수록 작은 수가 있으면 0번 인덱스까지 값을 확인해야함

# example code
def insertion_sort(data_list):
    for i in range(len(data_list)):
        for j in range(i, 0, -1):  # (시작, 종료, step)
            if data_list[j] < data_list[j - 1]:
                temp = data_list[j - 1]
                data_list[j - 1] = data_list[j]
                data_list[j] = temp  
            else:
                break
    return data_list

# 내가 작성한 코드
def insertion_sort2(i_list):
    for idx in range(1, len(i_list)):
        position = idx
        temp_val = i_list[idx]

        while position > 0 and i_list[position - 1] > temp_val:
            i_list[position] = i_list[position - 1]
            position = position - 1
        i_list[position] = temp_val
    return i_list

시간복잡도

주어진 데이터의 원소 길이가 5일때 두수의 비교를 순차적으로 끝까지 하게 되면 총 4번의 횟수가 발생한다.

이때 끝까지 비교를 하면 4+3+2+1 = 10번이 발생한다. (n-1) + (n-2) ... + 1

시프트(이동) 또한 4+3+2+1 = 총 10번이 걸리게 된다.

최악의 경우 O(N^2) 시간복잡도를 가지게 되며, 이미 정렬되어 있는 최선의 경우 비교만 하고

이동이 필요하지 않기에 O(N)의 시간복잡도를 가진다.