C# 삽입 정렬(Insertion Sort)에 대해서

삽입 정렬

삽입 정렬에 대해서 딱 들었을 때 드는 생각은 별도의 원소를 삽입하는 건가라는 생각이었다.

하지만 걱정하지 말자 추가적으로 원소를 삽입하거나 하지 않는다.

 

마치 손에 든 카드를 정렬하는 과정처럼 요소가 '마치' 삽입되기 때문에 삽입 정렬일 거라는 생각 한다.

(버블 정렬의 경우 큰 수는 무조건 맨 뒤로 간다.)

 

• 2번째 요소부터 시작한다. 1번째 요소와 비교해서 1번째 요소보다 작으면 1번째 요소 앞에 배치한다.
• 3번째 요소로 이동한다. 1번째 요소와 2번째 요소와 비교한다. 
• 이 과정을 배열의 길이 n - 1까지 반복한다.

 

시간 복잡도와 공간 복잡도

• 최고 시간 복잡도: O(n)
• 평균 시간 복잡도: O(n^2)
• 최악 시간 복잡도: O(n^2)
• 최고 공간 복잡도: O(1)

 

수도 코드(Pseudo Code)

Initialize n = Length of Array
InsertionSort(Array, n)
{
    for i = 1 to n-1
    {
        value = Array[i]
        position = i
        while (position > 0 and Array[position-1] > value)
        {
            Array[position] = Array[position - 1]
            position = position - 1
        }
        Array[position] = value;
    }
}

 

예제 코드

static void Main(string[] args)
{
    var array = new int[] { 3, 2, 6, 5, 1 };

    Console.WriteLine($"{string.Join(" ", array)} << 시작");

    InsertionSort(array);
}

public static int[] InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        for (int j = i; 0 < j; j--)
        {
            if (array[j] < array[j - 1])
            {
                var temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;

                Console.WriteLine(string.Join(" ", array));
            }
        }
    }

    return array;
}

 

정렬 과정

 

함께 보면 좋은 글

C# 버블 정렬(Bubble Sort)에 대해서

C# 선택 정렬(Selection Sort)에 대해서

 

참고 사이트

C# - Insertion sort