C++ / Algorithm 삽입 정렬(Insertion Sort)

삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교해 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘입니다. 

매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교해 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣습니다. 

 

정렬 프로세스 

1. 2번째 원소부터 시작한다.

2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다. (타겟 원소는 임시 변수에 넣는다.)

3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다. 

4. 이전 데이터도 차례대로 비교하며 정렬해나간다. 

5. 이 매커니즘으로 반복해 정렬한다. 

 

삽입 정렬 예시(Wikipedia)

삽입 정렬의 특징 

• 구현이 간단하다.
• 배열이 길어질수록 효율이 떨어진다.
• 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 비해 빠르고 안정 정렬이다.
• 데이터를 비교하면서 찾아서 비교정렬이다. 
• 추가적인 공간을 필요하지 않기 때문에 제자리 정렬(in-place-sort)이다.
• 데이터를 서로 교환(Swap)하면서 임시변수가(tmp)가 필요하다. 

시간 복잡도

- 최선의 경우

     - 이동없이 한 번씩 비교할 경우

     - T(n) = O(n)

 

- 최악의 경우 

     - 비교할 때 마다 i 번씩 비교

     - 각 단계마다 원소 이동

     - 1+2+3+4+...+(n-1) = n(n-1)/2 번 비교

     - T(n) = O(n^2)

 

예시

 

int main()
{
    int a[100],n, tmp,i,j;

    scanf("%d", &n);
    
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    // 두 번째 칸 기준잡기
    for(i = 1; i < n; i++)
    {
        tmp = a[i];
        for( j = i -1 ; j >= 0; j--)
        {
            // 오름차순
            if (a[j] > tmp)
            {
                // 큰 수를 오른쪽으로 이동시키고
                a[j + 1] = a[j];
            }
            else
            {
                // 더 이상 큰 수가 없다면
                break;
            }
        }
        // 임시 변수에 보관해뒀던 a[i] 를 a[j+1]에 대입하며 정렬
        a[j + 1] = tmp;
    }

    for(i = 0; i < n; i++)
    {
        printf_s("%d ", a[i]);
    }


    return 0;
}