삽입 정렬 알고리즘(Insertion Sort)

인프런 - 파이썬으로 배우는 알고리즘 기초 강의 이미지

✔ 삽입 정렬(Insertion Sort)

삽입 정렬은 적절한 위치에 삽입하여 정렬하는 알고리즘입니다.

삽입 정렬은 리스트의 두 번째 인덱스부터 시작해서 자기 기준의 왼쪽으로 비교하면서 정렬합니다.

또한, 자기 기준 왼쪽 부분은 정렬된 상태라 가정이 되기 때문에 적절한 위치를 파악할 수 있습니다.

 

예를 들면 [1, 2, 5, 4]인 리스트가 있을 때 현재 세 번째까지 정렬이 완료된 상태고 오름차순이라 가정하겠습니다.

네 번째와 자기 기준 왼쪽 값을 비교해서 자리를 변경하고, 다시 두 번째와 비교를 하지만 두 번째가 더 작기 때문에

변경이 발생하지 않습니다. 그리고 첫 번째는 이미 정렬된 상태여서 더 작은 값이기 때문에 아무 일도 일어나지 않습니다.

 

그래서 선택, 버블, 삽입 정렬 중에는 가장 적은 연산 횟수를 가지고 있습니다.

 

✔ 삽입 정렬 동작 과정

왼쪽 → 오른쪽 순으로 봐주시기 바랍니다.

 

1. 리스트의 두 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 첫 번째 인덱스를 비교해서
   교환 대상의 값이 더 크면 넘어가고, 더 작으면 위치를 교환합니다
2. 리스트의 세 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 두 번째 인덱스를 비교해서
   교환 대상의 값이 더 크면 넘어가고, 더 작으면 위치를 교환하고 다시 두 번째 인덱스와 첫 번째 인덱스의 값을 비교해서
   교환 대상의 값이 더 크면 넘어가고, 더 작으면 위치를 교환합니다
3. 리스트의 네 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 세 번째 인덱스를 비교해서
   교환 대상의 값이 더 크면 넘어가고, 더 작으면 위치를 교환하고 다시 세 번째 인덱스와 두 번째 인덱스의 값을 비교해서
   교환 대상의 값이 더 크면 넘어가고, 더 작으면 위치를 교환하고 두 번째 인덱스와 첫 번째 인덱스의 값을 비교해서
   교환 대상의 값이 더 크면 넘어가고, 더 작으면 위치를 교환합니다
4. 인덱스를 증가시키면서 교환 대상의 왼쪽 기준으로 비교해가면서 정렬합니다(반복)

※ 교환 대상의 기준 왼쪽 부분이 정렬되기 때문에 왼쪽에는 정렬이 된 상태라 가정이 됩니다

 

✔ 삽입 정렬 구현(C++)

#include <iostream>
using namespace std;

const int LEN = 7;
int arr[LEN] = {2, 9, 5, 6, 4, 1, 7};

void InsertionSort(int *arr, int len) {
    int j, temp;
    for(int i = 1; i < len; ++i) {
      temp = arr[(j=i)];
      // 왼쪽으로 비교해 간다
      while(--j >= 0 && temp < arr[j]) {
        arr[j+1] = arr[j];
      }
      arr[j+1] = temp;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    InsertionSort(arr, LEN);

    for(int i : arr)
      cout << i << " ";
    return 0;
}

 

✔ 삽입 정렬 시간 복잡도

삽입 정렬의 시간 복잡도는 아래와 같다.

$$ O(N^2) $$

 

(N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2 = N * N = O(N^2)

 

선택 정렬, 버블 정렬과 마찬가지로 같은 시간 복잡도이지만 셋 중에는 가장 효율적인 알고리즘이다.

연산 횟수가 셋 중에는 가장 적게 이루어진다.

시간 복잡도에 대한 좀 더 자세한 내용은 아래의 내용에서 확인하세요.
시간 복잡도

 

🔗 Reference

• 삽입 정렬
• 위키 백과(삽입 정렬)