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

설명

삽입 정렬은 현재 위치에서, 그 다음 배열들을 비교하며 자신이 들어갈 위치를 찾아 삽입하는 알고리즘이다

 

기본 로직

1. 두 번째 Index부터 시작
2. 현재 Index는 별도의 변수에 저장하고, 비교 Index는 현재 Index - 1로 설정
3. 별도로 저장해 둔 변수의 값과 비교 Index의 값을 비교
4. 저장된 변수의 값이 더 작으면 현재 비교 Index로 저장, 비교 Index - 1하여 비교를 반복
5. 저장된 변수의 값이 더 크면, 비교 Index + 1에 저장

시간 복잡도

최악의 경우 n-1, n-2, ... , 1개를 반복하여 O(n^2)

이미 정렬되어 있는 경우 1번씩만 하기 때문에 O(n)

 

코드

void InsertionSort(vector<int> v)
{
    for(int i = 0; i < v.size(); i++)
    {
    	int key = v[i];
        int j = i-1;
        
        while(j >= 0 && key < v[j])
        {
            swap(v[j], v[j+1]);
            j--;
        }
        v[j+1] = key;
    }
}