[알고리즘] 정렬 - (2) 삽입 정렬

2. 삽입 정렬

삽입 정렬은 앞서 했던 선택 정렬에 비해 구현 난이도는 높지만, 실행 시간 측면에서 더 효율적인 알고리즘이다.

특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효과적이다.

선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

삽입 정렬은 특정한 데이터를 적정한 위치에 삽입한다는 의미에서 삽입 정렬 (Insertion sort)이라고 부른다.

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞의 데이터는 이미 정렬되어 있다고 가정한다.

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 다음, 그 위치에 삽입된다는 점이 특징이다.

아래와 같이 초기 데이터가 구성되어 있다고 가정한다.

삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

**step 0️⃣ : 첫 번째 데이터 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈 지 판단한다. '7'의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 카드를 오름차순으로 정렬하기 위해 '7'의 왼쪽에 삽입한다.

step 1️⃣ : 이어서 '9'가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 '9'는 '5'와 '7'보다 크기 때문에 원래 자리 그대로 둔다.

**step 2️⃣ : 이어서 '0'이 어떤 위치에 들어갈지 판단한다. '0'은 '5', '7', '9' 와 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입한다.

stqp 3️⃣ : 이어서 '3'이 어떤 위치에 들어갈지 판단한다. '0'과 '5' 사이에 삽입한다.

stqp 4️⃣ : 이어서 '1'이 어떤 위치에 들어갈지 판단한다. '0'과 '3' 사이에 삽입한다.

stqp 5️⃣ : 이어서 '6'이 어떤 위치에 들어갈지 판단한다. '5'와 '7' 사이에 삽입한다.

stqp 6️⃣ : 이어서 '2'가 어떤 위치에 들어갈지 판단한다. '1'과 '3' 사이에 삽입한다.

stqp 7️⃣ : 이어서 '4'가 어떤 위치에 들어갈지 판단한다. '3'과 '5' 사이에 삽입한다.

stqp 8️⃣ : 이어서 '8'이 어떤 위치에 들어갈지 판단한다. '6'과 '7' 사이에 삽입한다.

stqp 9️⃣ : 이와 같이 적절한 위치에 삽입하는 과정을 N - 1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된 것을 확인할 수 있다.

아래는 정렬이 완료된 상태이다.

1) insertionSort.py

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까지 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

2) 삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다.

실제로 수행 시간을 테스트해보면 앞서 다뤘던 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있다.

여기서 꼭 기억해야할 점은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다.

최선의 경우 O(N)의 시간 복잡도를 가진다.

퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효율적이나, 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다.

따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.