📒 갈무리 - 삽입정렬(Insertion Sort)

📌 삽입정렬이란?

- 앞의 숫자가 현재 숫자보다 큰지 비교하며 자신의 위치에 삽입되는 정렬 방법

- 앞의 값과 비교를 하기 때문에 전체 배열 중 0번 인덱스가 아닌 1번 인덱스부터 앞의 값과 비교

- 정렬된 부분과 정렬되지 않은 부분을 나누어서 정렬되지 않은 데이터들을 정렬된 데이터와 비교해서 정렬하는 방식

- 앞에 비교한 데이터들은 이미 정렬된 데이터라고 간주한다.

 

📌 직접 구현해 보자...

// C#
        public void InsertionSort(int[] data)
        {

            for (int i = 1; i < data.Length; i++)
            {
                for (int j = i; j > 0; j--)
                {
                    if (data[j - 1] > data[j])
                    {
                        Swap(ref data[j - 1], ref data[j]);
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        public void Swap(ref int number1, ref int number2)
        {
            int temp = number1;
            number1 = number2;
            number2 = temp;
        }
        // 가독성을 위해 각 기능마다 함수로 분리하면 좋지만, 지금은 편의상 간단하게 구현함

 

📌 삽입정렬의 특징

- 선택정렬이나 거품정렬과 같은 O(n²)의 시간 복잡도를 갖는다.

- 비교할 데이터가 많은 경우에 효율이 좋지 않다.

ex) 내림차순으로 정렬되어 있는 데이터를 오름차순으로 바꾸어야 할 때

- 거의 정렬이 완료된 데이터들을 정렬할 때 매우 유리하다.