[Algorithm] Sort #3 - 삽입 정렬 Insertion Sort

삽입 정렬이란?

 기준 숫자를 정렬된 리스트에 삽입해 정렬하는 알고리즘

 

시간 복잡도

최상 : \( O(n) \)

최악 : \( O(n^2) \)

 

관련 글

[Algorithm] Sort #1 - 버블 정렬 Bubble Sort

[Algorithm] Sort #2 - 선택 정렬 Selection Sort

[Algorithm] Sort #4 - 병합 정렬 Merge Sort

[Algorithm] Sort #5 - 힙 정렬 Heap Sort

[Algorithm] Sort #6 - 퀵 정렬 Quick Sort

 

---

 

 정렬 알고리즘에 있어 기본인 버블 정렬, 선택 정렬 다음으로는 삽입 정렬입니다.

 

알고리즘

 삽입 정렬의 알고리즘은 다음과 같습니다.

1. 기준 값을 정한다..
2. 기준 값을 정렬된 원소들과 하나씩 비교해 알맞은 자리에 위치시킨다.
3. 1,2의 과정을 n-1번 진행한다.

 

삽입 정렬 예시

{ 9, 1, 7, 5, 2} 순서대로 원소가 존재한다고 가정했을 때 삽입 정렬의 예시는 다음과 같습니다.

 

 

 삽입 정렬도 선택 정렬과 같이 버블 정렬에 비해 과정이 단순해 보이지만 위 그림에서는 생략된 부분이 있습니다. 생략된 것은 바로 삽입 과정에서 정렬된 원소들과의 비교 과정입니다. 기준 값을 정렬된 원소에 넣기 위해서는 정렬된 원소의 맨 뒤부터 순차적으로 비교해야 합니다. 비교 과정에서 기준 값보다 작은 숫자를 찾았다면 해당 원소 바로 뒤에 위치시킵니다.

 

시간 복잡도 계산

 삽입 정렬의 시간 복잡도는 최악, 최상의 경우가 다릅니다. 

 

최상

 최상의 경우라면 이미 모든 원소들이 정렬되어 있는 상태입니다. 이 때는 기준 값과 정렬된 리스트 중 오직 마지막 원소만 비교할 뿐만 아니라 알맞은 자리에 위치시키는 과정 또한 생략되기 때문에 총 n-1번만 진행됩니다. 그래서 시간 복잡도는 \( O(n) \)입니다.

 

최악

 하지만 최악의 경우라면 모든 원소들이 정렬의 역순으로 있는 상태입니다. 이 때는 기준 값 하나를 위치시킬 때마다 1,2, ... n-2, n-1번 비교해야 합니다. 이 과정을 n-1번 하기 때문에 시간 복잡도는 \( O(n^2) \)입니다.

 

 

 최악의 경우 이전 글에서 설명한 버블 정렬, 선택 정렬과 비슷한 수준이지만 최상의 경우에 가까워질수록 삽입 정렬이 두 정렬보다 매우 빠르다고 볼 수 있습니다.

 

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> arr = {9,1,7,5,2};
    vector<int> sorted_arr;
    sorted_arr.push_back(arr[0]);
    
    for(int i=1; i<arr.size(); i++){
        int pos = 0;
    
        for(int j=sorted_arr.size()-1; j>=0; j--){
            if(sorted_arr[j] < arr[i]){
                pos = j+1;
                break;
            }
        }
        
        sorted_arr.insert(sorted_arr.begin()+pos, arr[i]);
    }
    
    
    for(int i=0; i<sorted_arr.size(); i++)
        cout << sorted_arr[i];
}