삽입정렬

개념

삽입정렬은 배열을 정렬 된 영역과 정렬되지 않은 영역으로 본다. 정렬 된 영역의 옆에 붙은 원소를 정렬 된 영역을 앞에서부터 순회하면서 맞는 자리에 삽입하는 방식이다.

작동방식

오름차순으로 정렬할 때 작동방식은 다음과 같다. 인덱스 i에 있는 원소 a를 정렬할 차례일 때, 0 부터 i-1까지는 이미 정렬되어 있는 상태다. 정렬 된 영역의 원소를 하나씩 a와 비교하면서 a보다 크다면 shift를 하고 a보다 작다면 a를 삽입한다.

동작과정

파이썬

def insertion_sort(my_list: list):

    for i in range(1, len(my_list)):
        key = my_list[i]
        j = i
        while j > 0 and my_list[j - 1] > key:
            my_list[j] = my_list[j - 1]
            j -= 1
        my_list[j] = key

    return my_list

my_list = [5, 4, 3, 2, 1]
insertion_sort(my_list)

print(my_list)

CPP

void(vector<int> arr, int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i;
        for (; j > 0 && arr[j - 1] > key; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = key;
    }
}

특징

• 시간복잡도는 O(N^2)이다.
• 배열 전체가 정렬되어 있다면 O(N)이다. 이미 정렬 된 영역 때문에 삽입정렬시 한번의 비교로 순회여부를 결정할 수 있다.
• 삽입정렬은 재귀적 성격을 띄고 있다.