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

Insertion Sort(삽입정렬)의 방식은 이렇게 이해하면 쉽다.

내가 트럼프카드를 패로 쥐고 있고, 그게 오름차순으로 정렬되있다고 가정하자.

그러고 새 카드를 뽑으면 정렬된 패의 정렬순서에 맞게 새 카드를 어딘가에 삽입해야한다.

그것이 삽입정렬이다.

도식화 한 Insertion Sort

리스트 그림을 통해 삽입정렬의 작동원리를 보자!

0~5번째 위치까지 정렬된 리스트 6번째 위치에 5라는 숫자가 들어왔다.

마지막 위치에 있는 5를 key라고 하자.

key는 왼쪽으로 움직이면서 어디에 들어갈지 본다.

key가 왼쪽으로 움직이면서 앞자리와 숫자 대소비교를 하게된다.

5번째 자리로간 key는 리스트의 5번째 원소인 13과 값을 비교한다.

이때 key > 13 이므로 5번째 원소의 값 13은 뒤로 밀려난다.

즉, 5번째 원소의 값을 원래 key가 있던 자리인 6번째로 복사한다.

위와 같은 과정을 반복하고 마침내 key < 원소 일때가 오면

비교하기를 멈춘다.

다음과 같은 처리를 수행하기 위해서 insert 함수를 만들어보았다.

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] array = {3, 5, 7, 11, 13, 2, 9, 6};
            
            Console.WriteLine("insert(array, 4, 2) 이후 ");
            insert(array, 4, 2);
            printArray(array);
            
            Console.WriteLine("insert(array, 5, 9) 이후 ");
            insert(array, 5, 9);
            printArray(array);
            
            Console.WriteLine("insert(array, 6, 6) 이후 ");            
            insert(array, 6, 6);
            printArray(array);
            
        }
        // insert() 함수 호출 전
        // array[0]부터 array[rightIndex]까지는 오름차순 정렬이 되어 있어야함.
        public static void insert(int[] array, int rightIndex, int val) {
            int i;
            for (i = rightIndex; (i >= 0) && (array[i] > val); i--) {
                array[i + 1] = array[i];
            }
            array[i + 1] = val;
        }
        
        public static void printArray(int[] array) {
            foreach (int element in array) {
                Console.Write(element + " ");
            }
            Console.WriteLine();
        }
    }
}
                 
                 
                 

주어진 array에서 제대로 정렬된 부분까지의 index 값을 rightIndex 라고 한다.

그리고 rightIndex에서부터 왼쪽으로 찬찬히 비교해나가는 key값이 val이다.

rightIndex에서부터 왼쪽으로 비교하면서 그 값보다 val이 클 경우에는 그 자리 다음에 val 값을 대입하는 방식이다.

위 코드 수행 결과는 아래와 같다.

insert 함수를 구현했으니 이제 insertionSort를 구현해보도록 하겠다.

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] array = {3, 5, 7, 11, 13, 2, 9, 6};  
            insertionSort(array);
            printArray(array);
        }
        
        public static void insertionSort(int [] array) {
            for (int i = 1; i < array.Length - 1; i++) {
                insert(array, i, array[i + 1]);
            }
        }
        
        public static void insert(int[] array, int rightIndex, int val) {
            int i;
            for (i = rightIndex; (i >= 0) && (array[i] > val); i--) {
                array[i + 1] = array[i];
            }
            array[i + 1] = val;
        }
        
        public static void printArray(int[] array) {
            foreach (int element in array) {
                Console.Write(element + " ");
            }
            Console.WriteLine();
        }
    }
}

무작위 array에서 정렬되어있다고 할 수 있는 자리 수는 첫번째 자리 뿐이므로

2번째 부터 insertionSort를 시작한다. 이 자리를 i = 1이라고 명시했다.

그리고 array index bound를 넘지 않도록 array.Length - 1이라고 해주었다.

그러면 2번째 자리부터 다음 자리를 돌면서 insertionSort가 수행된다.

수행 결과는 아래와 같다.