[알고리즘] 삽입정렬

안녕하세요

이번에는 삽입정렬에 대하여 알아보려고합니다.

예제코드는 파이썬으로 진행합니다.

---

삽입정렬(Insert Sort) 이란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

---

삽입정렬의 과정

삽입정렬은 두번째 요소부터 시작하여, 

그 앞(왼쪽)의 자료들과 비교하고 나머지는 뒤(오른쪽)으로 한칸씩 이동시키는 알고리즘입니다.

이게 무슨말이냐 함은 리스트로 [3, 7, 2, 5, 1,4] 라는 리스트가 주어졌다고 가정해봅시다.

이제부터 이 리스트를 삽입정렬을 이용하여 오름차순으로 정렬해보도록 합시다.

1. 두번째 요소인 7을 앞[3] 과 비교합니다. 7은 3보다 크기 때문에 동일한 자리에 위치합니다.
2. 세번째 요소인 2를 앞[3, 7] 과 비교합니다. 2는 3 보다 작기 때문에 맨 앞자리로 이동시켜 주며, 나머지 3, 7은 뒤(오른쪽)으로 한칸씩 이동합니다.
3. 네번째 요소인 5를 앞[2, 3, 7] 과 비교합니다. 5는 3보단 크고 7보단 작기 때문에 3과 7사이로 이동하며 7부터 뒤(오른쪽)으로 한칸씩 이동합니다.
4. 다섯번째 요소인 1을 앞[2, 3, 5, 7]과 비교합니다. 1은 앞의 모든 요소보다 작기 때문에 맨 앞으로 이동하며, 나머지는 뒤(오른쪽)으로 한칸씩 이동합니다.
5. 여섯번째 요소인 4를 앞[1, 2, 3, 5, 7]과 비교합니다. 4는 3보단 크고 5보단 작기 때문에 3과 5사이로 이동하며, 나머지는 뒤(오른쪽)으로 한칸씩 이동합니다.

A,B,C,D,E의 각각을 1회전으로 부릅니다. 따라서 다음과 같은 리스트는 5회전을 하여 오름차순 정렬이 완료되었다고 볼 수 있습니다.

---

삽입정렬의 특징

• 삽입정렬은 정렬대상의 대부분이 이미 정렬되어 있을 경우 매우 효율적이다.
• 정렬할 요소들이 많다면, 한칸씩 뒤로 이동해야하기때문에 속도면에서 현저히 느려질 수 있다.

---

파이썬 코드확인

def insert_sort(value_list):
    for num1 in range(1, len(value_list)):           # 두번째 요소부터 시작한다.
        val = value_list[num1]                       # 비교하려는 값을 변수에 넣어준다.
        for num2 in range(num1 - 1, -1, -1):         # 비교하려는 값과 앞에있는 모든 수가 범위이다.
            if value_list[num2] > val:               # 만약 비교하려는 값이 더 작다면 기존 리스트들을 한칸씩 밀어준다.
                value_list[num2 + 1] = value_list[num2]
            else:                                    # 아닌 경우 비교하려는 값을 삽입한다.
                value_list[num2 + 1] = val
                break
    return value_list
    
    
print(insert_sort([1,5,2,4,7,3]))
 

---

삽입정렬의 시간복잡도

for 반복문이 두번 중첩되어있으며, 범위는 리스트의 길이에 따라 달라지기 때문에

빅오 표기법을 사용하면 n²만큼의 시간복잡도가 됩니다.

---

References

• 선택 정렬 - 위키백과