삽입 정렬

삽입 정렬은 배열을 최소 단위에서 하나씩 늘려가며 정렬을 실행한다. 

 

배열의 다음 데이터를 확인하고 그 데이터의 알맞은 자리를 찾아 입력하게 된다. 

 

이 과정이 데이터를 꺼내 알맞은 자리에 삽입하는 것처럼 보여 삽입 정렬이다.

 

삽입 정렬은 버블 정렬과 비슷한 구현 난이도에 비슷한 성능이지만, 장점이 있다.

 

이미 정렬된 집합의 경우 삽입 정렬이 성능이 월등히 좋아진다.

void InsertionSort(int DataSet[], int Length)
{
    int i = 0;
    int j = 0;
    int value = 0;

    for (i = 1; i < Length; i++)
    {
        if (DataSet[i - 1] <= DataSet[i])
            continue;

        value = DataSet[i];

        for (j = 0; j < i; j++)
        {
            if (DataSet[j] > value)
            {
                memmove(&DataSet[j + 1], &DataSet[j], sizeof(DataSet[0]) * (i - j));
                DataSet[j] = value;
                break;
            }
        }
    }
}