[알고리즘] 삽입 정렬 ( Insertion Sort )

1. 개념

버블 정렬과 같이 단순 비교문을 이용하여 정렬하고자 하는 값를 옴겨 놓는 방식은 비슷하나

키( Key )에 해당하는 값을 정하고 앞쪽의 하나씩 비교 대상 값과 비교하여 위치를 옴겨 놓는 방식

- key 값은 배열의 두번째 인덱스 값부터 시작하며 1회당 인덱스를 1씩 증가시켜 배열의 끝까지 도달합니다.

- 비교 대상 ( compare ) 값은 key 인덱스보다 -1 낮은 인덱스부터 시작하며 1회당 -1씩 감소 시켜 배열의 처음까지 도달합니다.

- 비교 조건(오름차순, 내림차순)에 해당한다면 값을 교환 변경 합니다.

key의 시작 인덱스 : 1

comare의 시작 인덱스 : 0

위의 사진과 조건에 해당할때만 값의 복사가 일어나서 버블 정렬과 다르게 시간을 단축시키는 요소가 생깁니다.

2. C# 코드

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nArr = new int[]{ 1, 4, 3,  5, 9, 6, 2, 7, 8, 10 };

            // nKey : 키 값
            // nCompareIndex : 비교 값이 되는 인덱스
            // nCount : 값의 교환 횟수
            int nKey, nCompareIndex, nCount; 
            nCount = 0;

            // 코드의 이해를 돕기위해 반복문의 인자 값을 이용목적으로 변수이름을 사용
            // 시작 키 인덱스 : 1
            for (int KeyIndex = 1; KeyIndex < nArr.Length; KeyIndex++)
            {
                nKey = nArr[KeyIndex];

                // 시작 비교 인덱스 : 0
                // nArr[nCompareIndex] > nKey : 오름차순
                // nArr[nCompareIndex] < nKey : 내림차순
                for (nCompareIndex = KeyIndex - 1; nCompareIndex >= 0 && nArr[nCompareIndex] > nKey; nCompareIndex--)
                {
                    nArr[nCompareIndex + 1] = nArr[nCompareIndex];
                    nCount++;
                }

                nArr[nCompareIndex + 1] = nKey;
            }

            Console.WriteLine("Count : {0}", nCount);

            for (int i = 0; i < nArr.Length; i++)
                Console.Write(nArr[i] + "\t");

        }
    }
}

결과

Count : 9 1    2    3    4    5    6    7    8    9    10

3. 장단점

장점

    - 비교적 쉬운 코드로 구현 가능

    - 데이터의 크기가 작을 수록 복잡한 코드로 구현된 정렬보다 빠를수 있음

    - 같은 구현 난이도의 버블 정렬보다 정렬 속도의 이점을 가지고 있음

단점

    - 데이터의 크기가 커질수록 효율이 떨어짐

    - 최악의 경우 비교 횟수와 교환 횟수가 버블정렬과 같이 n의 2승만큼 커질수 있음

정렬 알고리즘 테스트

종류	최소	최대	정렬시간 (10만개 테스트)
퀵 정렬	n log n	n2	32 ms
삽입 정렬	n	n2	8142 ms
선택 정렬	n2	n2	13499 ms
버블 정렬	n2	n2	53488 ms

단적인 측면에서는 버블 정렬보다는 빠르지만 근본적인 효율에서는 비효율적인 방법 입니다.

4. 관련글

• 버블 정렬 ( Bubble Sort ) Post 참고
• 선택 정렬 ( Selection Sort ) Post 참고
• 퀵 정렬 ( Quick Sort ) Post 참고