삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 데이터를 하나하나씩 확인
• 선택 정렬에 비해 난이도가 높지만 더 효율적

---

1. 삽입 정렬 동작 예시

[Step 0]

출처 : 이코테2021

• 7은 그 자체로 정렬되어 있다고 판단하고 이 다음 데이터인 5가 어떤 위치로 들어갈지 판단한다.
• 7보다 작으면 7의 왼쪽(파란색 화살표)
• 7보다 크면 7의 오른쪽(회색 화살표) 로 들어간다.
• 5는 7보다 작으므로 왼쪽으로 들어갈 것이다.

 

[Step 1]

• 5가 7의 왼쪽으로 삽입되었다.
• 다음으로 9가 어떤 위치로 들어갈지 판단한다.
• 9는 7보다 작으면 왼쪽으로 갔을 것이고 또 5보다 작았으면 왼쪽으로 갔을 것이다.
• 여기서는 7보다 크므로 그자리에 그대로 있는다.

 

[Step 2]

• 그다음 위치에 있는 0을 비교한다.
• 0은 그 앞 수들보다 모두 작으므로 왼쪽에 있는 수부터 계속 비교해서 가장 첫번째 수인 5앞으로 이동시킨다.

 

• 정렬이 완성된다.

---

2. 삽입 정렬 소스코드

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): #인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:#자기보다 작은 데이터를 만다면 그 위치에서 멈춤
            break
print(array)

• 첫 번째 원소는 정렬되있다고 가정하고 첫 번째 원소부터 반복문을 실행한다.
• 두 번째 반복문은 i부터 1까지(0 보다 큰거이므로) -1씩 감소시켜 확인한다.
• 매번 왼쪽이랑 비교해서 그 값이 작다면 계속해서 바꿔준다.
• 자기보다 작은 원소를 만나면 멈추면 된다.

---

3. 삽입 정렬의 시간 복잡도

• 선택 정렬과 마찬가지로 반복문이 두 번 중첩되서 사용된다.
• 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
• 최선의 경우 O(N)의 시간 복잡도를 가진다.