자료구조) 삽입 정렬 (Insertion Sort)

삽입 정렬은 필요할 때마다 데이터를 하나씩 정렬된 부분에 삽입하는 방식이다.

삽입 정렬은 아래와 같은 순서로 진행된다.

1. 정렬되지 않은 다음 데이터를 선택한다.
2. 선택 된 데이터를 임시 저장한다.
3. 정렬된 데이터를 다음 인덱스로 덮어 씌우며, 임시 저장된 데이터와 비교한다.
4. 비교 조건에 따라 임시 저장된 데이터를 리스트 인덱스에 삽입한다.

void InsertionSort(int* list, int size)
{
    for (int i = 1; i < size; i++)
    {
    	int j = i;
        int temp = list[i];
        // 비교
        for (; j > 0 && list[j - 1] > temp; j--)
        {
            list[j] = list[j - 1];
        }
        // 삽입
        list[j] = temp;
    }
}

참조) Insertion sort - Wikipedia