삽입 정렬

삽입 정렬

정렬할 배열의 원소를 하나씩 빼서 정렬한다.

보통 배열을 하나 더 만들어서 값을 복사해오면서 정렬할거라 생각할수 있지만 실제로는 그렇게 구현하지 않고, 정렬할 배열의 왼쪽, 오른쪽 등의 기준으로 나누어 정렬한다.

결국 시간복잡도 O(N^2) 이다.. 일반적으로 효율 안좋다.

 

배열을 안쪽 for 문을 돌 때 마다 인덱스 i 까지의 배열 요소들이 정렬된다.

예) i == 3 이면 v[0]~v[3] 까지의 요소들이 정렬된다. 즉, 안쪽 for 문 돌 때마다 정렬이 특정 범위까지 계속 일어난다. 

 

void InsertionSort(vector<int>& v)
{
    const int n = (int)v.size();

    for (int i = 1; i < n; ++i)
    {
        int iData = v[i];

        int j;
        for (j = i - 1; j >=0; --j)
        {
            if (v[j] > iData)
            {
                v[j + 1] = v[j];
            }
            else
                break;
        }

        v[j + 1] = iData;
    }
}