삽입 정렬 (Insertion Sort)

• 시간 복잡도는 O(n^2) 이다.

코드

void InsertionSort(int[] array)
{
    int k = 0;
    int j = 0;
    for (int i = 1; i < array.Length; ++i)
    {
        k = array[i];
        j = i;
        while (j > 0 && array[j - 1] > k)
        {
            array[j] = array[j - 1];
            --j;
        }

        array[j] = k;
    }
}

테스트 코드

int[] array = { 10, 5, 7, 2, 8, 4, 1 };
InsertionSort(array);

풀이

i = 1로 for loop가 실행된다.

이때 k = 5, j = 1 이 된다.

while 문의 조건식에 따라

j가 0보다 크고, k보다 array[j - 1] 가 클때까지 while 문을 실행한다.

while 문 실행 끝났을 경우 array의 값은 아래와 같이 바뀌어 있다.

10, 10, 7, 2, 8, 4, 1

j = 0 으로 바뀌어 있고 array[j] = k 처리를 수행한다.

한번의 for loop문으로 array는 아래와 같이 바뀌어 있다.

5 10 7 2 8 4 1

이와 같이 i < array.Lenth 만큼 for loop를 수행하면서

0 ~ j 의 범위의 array 값을 정렬한다.