삽입 정렬 (C#)

개요

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

처음 Key 값은 두 번째 자료부터 시작한다.

 

시간복잡도

O(N²)

들어갈 위치를 선택할 때 N 번,

선택하는 횟수 N 번

(일반적으로 선택 정렬보다 조금 빠르다.)

 

최선의 경우는 O(n)

 

class 삽입정렬
    {
        static void Main(string[] args)
        {
            int[] array = { 10, 9, 6, 3, 8, 1 };
 
 
            for (int i = 0; i < array.Length - 1; i++)
            {
                int j = i;
                while (j >= 0 && array[j] > array[j + 1])
                {
                    Swap(ref array[j], ref array[j + 1]);
                }
            }
 
            for (int i = 0; i < array.Length; i++)
                Console.WriteLine(array[i]);
        }
 
        private static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
    }