[정렬 알고리즘, C#] 삽입 정렬(Insertion Sort)

■ 삽입 정렬(Insertion Sort)

삽입 정렬은 사람이 수를 정렬할 때 사용하는 방식과 매우 유사하게 동작한다.

예를 들어, 손에 1부터 9까지 무작위로 섞인 카드를 들고 있다고 생각해 보자. 그럼 우리는 가장 왼쪽부터 카드를 꺼내, 앞쪽에 이미 정렬된 카드 들 중에서 자신이 들어갈 위치를 찾아 끼워 넣는 방식으로 정렬한다.

삽입 정렬도 이와 같은 방식으로 동작한다.

[삽입 정렬 원리]

삽입 정렬은 현재 선택된 값을 정렬된 앞쪽 부분과 비교하면서, 자신이 들어갈 적절한 위치를 찾아 삽입한다.

1. 오름차순 정렬 기준으로, 현재 값보다 앞들에 있는 값이 큰지 확인한다.
2. 값이 크다면, 그 값들을 한 칸씩 뒤로 밀어내면서 빈 자리를 만든다.
3. 만들어진 빈 자리에 현재 값을 삽입하여 정렬한다.

 

■ 삽입 정렬 구현(C#)

public static class SortArray<T> where T : IComparable<T>
{
    // 삽입 정렬
    public static void InsertionSort(T[] arr)
    {
        for(var i = 1; i < arr.Length; ++i)
        {
            var temp = arr[i];
            var j = i - 1;

            while (j >= 0 && arr[j].CompareTo(temp) > 0) 
            {
                // 큰 값 밀어내기
                arr[j + 1] = arr[j];
                j--;
            }

            // 이렇게 되면 j + 1이 비어있는 위치가 됨.
            arr[j + 1] = temp;
        }
    }
}

삽입 정렬의 구현도 비교적 간단하다.

배열의 두 번째 요소부터 시작하여, 현재 위치(i)의 값을 임시로 저장하고, 그 앞에 있는 요소들(i-1부터 시작)과 비교해 가며 자신이 들어갈 위치를 찾는다.

• 만약 앞에 있는 값이 현재 값(temp)보다 작다면, 그보다 앞쪽은 이미 정렬되어 있다고 간주할 수 있다.
• 반대로 앞에 있는 값이 더 크다면, 해당 값을 한 칸 뒤로 밀어 비워주는 방식으로 temp가 들어갈 자리를 만들어준다.

이 과정을 반복한 뒤, 마지막에 남은 비어 있는 자리(j+1)에 temp를 삽입하면 한 단계의 정렬이 완료된다.

 

▶ 삽입 정렬의 시간복잡도

삽입 정렬은 중첩된 반복문을 사용하기 때문에, 최악의 경우에는 $O(n^2)$의 시간복잡도를 가진다.

• 하지만 배열이 어느정도 정렬되어 있는 상황에서는 불필요한 비교나 이동이 줄어들어 매우 빠르게 동작한다.
  • 이는 삽입 정렬이 앞쪽 원소들과 비교하면서 비교 조건이 만족되지 않으면 즉시 반복을 종료하기 때문이다.

따라서 삽입 정렬은 거의 정렬된 상태의 데이터에 대해선 최적의 성능을 낼 수 있으며, 이 경우 시간복잡도는 $O(n)$까지 떨어진다.

• 사실 대부분의 알고리즘도 운이 좋다면 $O(n)$의 성능을 낸다…