삽입 정렬(Insert Sort)에 대해 알아보자!

삽입 정렬

• 오름차순을 기준으로 정렬.
• 배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 해당 원소의 위치를 찾아 삽입하는 정렬.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-insertion-sort/insertion-sort.png>

---

삽입 정렬 C# 코드

public void Insert_Sort(int[] array)
    {
        int temp;

        for (int i = 1; i < array.Length; i++)
        {
            for (int k = i; k > 0; k--)
            {
                if (array[k] < array[k - 1])
                {
                    temp = array[k];
                    array[k] = array[k - 1];
                    array[k - 1] = temp;
                }
            }
        }
    }

 

• 장점
  - 비교적 안정한 정렬 방법.
  - 배열 원소의 수가 적을 경우 유리한 방법.
  - 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적임.
  
  
• 단점
  - 비교적 많은 원소들의 이동을 포함.
  - 원소의 수가 많고 크기가 클 경우에 부적합.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-insertion-sort/sort-time-complexity.png>

---