CHAPTER 6. 정렬 - 삽입 정렬

2. 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 하는 정렬 알고리즘

선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작한다. (선택 정렬에 비해 실행 시간 측면에서 더 효율적)

선택 정렬은 현재 데이터 상태와는 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다.

 

특징

• 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
• 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.
• 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단.

 

동작 예시

초기 데이터: 7 5 9 0 3 1 6 2 4 8

첫 번째 데이터 '7'은 이미 정렬이 되어있다고 판단.

 

[step 1] 두 번째 데이터 '5'가 어느 위치로 들어갈지 판단한다.'7'의 왼쪽 혹은 오른쪽 두 경우만 존재한다. 오름차순 정렬을 하는 경우 이므로 '7'의 왼쪽에 삽입.

→  '5', '7' 정렬 완료

 

[step 2] 세 번째 데이터 '9'가 어느 위치로 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3 가지이며 '9'는 '5', '7'보다 크기 때문에 원래 자리 그대로 둔다.

→  '5', '7', '9' 정렬 완료

 

[step 3] 네 번째 데이터 '0'이 어느 위치로 들어갈지 판단한다. 삽입될 수 있는 위치는 총 4 가지이며, '0'은 '5', '7', '9'와 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입한다.

→  '0', '5', '7', '9' 정렬 완료

 

 

---------- 중략 ----------

 

 

[step 10] 위의 과정을 총 9(n-1)번 반복하면 모든 데이터의 정렬이 완료된다.

→  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 정렬 완료

 

삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있기때문에 특정한 데이터가 삽입될 위치를 선정할 때(삽입될 위치를 찾기 위해 왼족으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 다시말해, 특정 데이터 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났을 때는 더 이상 살펴볼 필요가 없다.

 

 

시간 복잡도

삽입 정렬은 선택 정렬과 마찬가지로 이중 반복문을 사용하므로 시간 복잡도는 O(N²)라고 할 수 있다.(반복문 안에서 비교연산과 swapping 수행) 실제로 수행시간을 테스트해보면 선택정렬과 흡사한 시간이 소요되는 것을 알 수 있다. 하지만, 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 시간 복잡도는 O(N)으로 매우 빠르게 동작한다.

예를 들어, 오름차순 정렬을 수행할 때 이미 오름차순 정렬이 되어있다면 데이터가 들어갈 위치를 고르는 과정에서 단순히 왼쪽 데이터와 한번만 비교하고 바로 멈춘다. 때문에 이 과정이 상수시간(costant time)안에 가능해진다. 그래서 최선의 경우(이미 정렬이 되어 있는 경우) 전체 정렬을 위한 시간 복잡도는 O(N)이다.

 

 

Big-O Notation: Worst, Avg-O(N²) / Best-O(N)

 

공간 복잡도

정렬하고자 하는 배열 안에서 교환하는 방식, 다른 메모리 공간을 필요로 하지 않는다. →in-place

 

코드

# 삽입 정렬
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): # 선택한 원소부터 1까지 1씩 감소하면서 반복, 세 번째는 step
        if array[j] < array[j -1]: # j는 현재 삽입하고자하는 원소, 왼쪽에 있는 데이터와 비교했을 때 자기가 더 작으면 swap
            array[j], array[j-1] = array[j-1], array[j]
        else:# 현재 삽입하고자 하는 원소가 왼쪽에 있는 데이터보다 크거나 같다면 그 자리에서 멈추면 된다.
            break # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤

---

 

 

Q. 데이터가 거의 정렬되어 있는 상태에서의 삽입 정렬?

퀵 정렬과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어있는 상황에서는 퀵 정렬보다 더 강력하다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 다른 정렬 알고리즘을 이용하는 것 보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.