[Algorithm] 삽입 정렬(Insertion Sort)에 대해 알아보자!

이번에 다룰 내용은 여러 정렬 알고리즘 중 하나인 삽입정렬이다.

 

바로 삽입정렬의 개념부터 알아보자.

 

삽입정렬이란?

배열 값 중에서 비교할 키 값을 정해놓고 맨 앞 인덱스부터 하나씩 비교 키 값과 비교하여 작은 수를 앞으로 옮기는 방식이다. 풀어서 얘기하면 삽입정렬은 1번 인덱스부터 시작을 하며 2개의 수를 비교하여 배열 사이에 변수를 삽입하여 정렬하는데 이렇게 정렬을 하다보면 비교한 숫자보다 왼쪽으로 자신이 더 크면 그냥 원래 자리에 있는 방식이라서 순차적으로 계속 진행하면 정렬이 되는 형식이다.

 

아래의 참고 사진을 보면 이해에 도움이 될것이다.

https://dnmaxi.tistory.com/23

 

위의 사진을 보면 알 수있듯 키값을 정해두고 비교해가며 정렬해가는 방식인 것이다.

 

이제 삽입정렬의 장 단점을 알아보자.

 

장점

• 비교적 쉬운 코드로 구현이 가능하다.
• 선택, 버블 정렬보다 속도 측면에서 더 빠르다.
• 데이터의 크기가 작을수록 복잡한 코드로 구현된 정렬보다 빠를 수 있다.

단점

• 데이터의 크기가 커질수록 효율이 떨어지는 정렬이다. (이럴 때 퀵 정렬 추천!)
• 정렬 전 배열의 상태가 정렬이 잘 안맞아있고 그러면 복잡도가 O(n^2)가 될 수 있다.

 

정렬 알고리즘 테스트 결과

 

이제 소스를 보고 이해해보자.

(C# Source)

using System;

namespace Jeongkyun_InsertionSort
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] nArr = new int[] { 1, 7, 5, 34, 5, 2, 23, 54, 1 };
            nArr = arr_swap_insert_sort(nArr);
            Print(nArr);

            Console.ReadKey();
        }

        /// <summary>
        /// 삽입 정렬 + SWAP 로직 구현 함수
        /// </summary>
        /// <param name="arr">기존 배열 값을 담아둔 변수</param>        
        static int[] arr_swap_insert_sort(int[] arr)
        {
            int temp = -1;

            //인덱스 1번부터 검사
            for (int i = 1; i < arr.Length; i++)
            {
                // 0~ i의 인덱스 까지 검사
                for (int j = 0; j < i; j++)
                {
                    //arr[j]보다 비교대상이 크면 Swap 진행
                    if (arr[i] < arr[j])
                    {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }

                }
            }
            return arr;
        }

        /// <summary>
        /// Print 함수
        /// </summary>
        /// <param name="arr_val"></param>
        static void Print(int[] arr_val)
        {
            for (int i = 0; i < arr_val.Length; i++)
            {
                Console.Write(arr_val[i].ToString() + "\t");
            }
        }
    }
}