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

개요 및 정의하기

 

이번 포스팅에서는 기본 정렬 알고리즘인 삽입정렬에 대해 다룹니다. 

 

삽입정렬(Insertion Sort)

 

삽입 정렬은 정렬이 필요한 모든 요소들 처음부터 시작하여 이미 정렬된 배열부분 중 정렬이 필요한 요소의 위치를 찾아 삽입하여 정렬하는 방식입니다.

 

설명하기

 

삽입 정렬이 어떤 방식으로 정렬 되는지 직접 사진으로 분석해보겠습니다. 

 

 

3,7,2,5,1,4 라는 값을 정렬하려합니다. 

 

맨 처음 3은 정렬되어있다고 가정하고 7 부터 검사합니다. 7이 3보다 작은지 검사하고 그렇지 않은경우 다음 인덱스로 이동합니다. 

 

이제 3과 7까지 정렬되어있다고 가정하고 2의 값의 위치를 찾아갑니다. 2는 7보다 작기에 한칸 앞으로 당깁니다.

마찬가지로 2가 3보다도 작으므로 한칸 더 앞으로 당기면 (c) 와 같은 상태가 됩니다.

 

배열의 모든 요소를 방금과 같은 방식으로 정렬합니다. 

 

구현하기

 

이제 삽입 정렬을 직접 코드로 구현해보겠습니다. 우선은 구현하기 전에 필요한 변수와 로직부터 정리해보겠습니다. 

 

작성된 언어는 C# 입니다. 

 

먼저, 배열의 인덱스 변수가 필요합니다. 우선 위 사진에서 보이는 인덱스는 빨간색과 검은색이 있습니다. 빨간색은 정렬해야할 인덱스, 검은색은 정렬이 된 인덱스겠지요. 그래서 인덱스 변수도 둘을 생각해볼 수 있겠습니다. 

 

그리고 위 사진으로 확인되지는 않지만 앞서 삽입 정렬은 정렬할 요소를 이미 정렬된 요소들과 하나씩 비교하며 자리를 찾아가는 정렬이라 말씀드렸습니다. 비교할 값을 미리 저장해둘 변수가 있으면 좋겠네요.

 

public void InsertionSort(List<int> array)
{
    int curIndex; // 앞으로 정렬 되어야 할 요소의 인덱스
    int preIndex; // 이미 정렬 되어있는 요소의 인덱스
    int value; // 정렬 되어야할 요소의 값을 보관

}

 

필요한 변수는 이정도가 있겠습니다. 함수명은 InsertionSort 이고 매개변수로는 배열의 주소를 받아옵니다. 

 

이제 정렬 알고리즘의 핵심 부분인 반복문을 정의 해보겠습니다. 두 인덱스 변수는 둘 다 반복하지만 curIndex 는 앞으로 정렬 되어야할 요소들이고 preIndex 는 정렬 되어있는 배열의 인덱스 입니다.

 

따라서, curIndex 는 배열의 0번이 아닌 1번 요소부터 마지막 요소까지 검사할 것이고, preIndex 는 앞으로 정렬되어야 할 curIndex 의 바로 이전 인덱스 부터 시작하여 맨 앞 요소까지 하나씩 줄어들며 정렬 될 요소의 자리를 찾습니다. 

 

public void InsertionSort(List<int> array)
{
    int curIndex; // 앞으로 정렬 되어야 할 요소의 인덱스
    int preIndex; // 이미 정렬 되어있는 요소의 인덱스
    int value; // 정렬 되어야할 요소의 값을 보관
    
    for(curIndex = 1; curIndex < array.Count; curIndex++)
    {
    	value = array[curIndex]; // 정렬 되어야 할 요소 저장
        preIndex = curIndex - 1; // 정렬 되어야 할 요소의 인덱스 바로 이전 인덱스
        
        // preIndex 가 음수가 아니고 정렬 되어야할 요소가 이전 요소보다 작다면
        while(preIndex >= 0 && value < array[preIndex])
        {
       	    array[preIndex + 1] = array[preIndex]; // 이전 요소의 다음 자리에 이전 값 덮어씌우기
            preIndex--; // 한칸 앞으로 당기기
        }
        array[preIndex + 1] = value; // 올바른 자리에 저장해둔 value 덮어씌우기
    }
}

 

앞서 말한 반복문을 작성하면 정렬이 완성됩니다.  그 과정을 다시 정리해보겠습니다.

 

3, 7, 2, 1, 4 를 정렬하려 합니다. 

 

 

while 문을 들어가기 전 이러한 모습을 하고 있겠네요. 여기서 while 문으로 진입하기 위한 조건을 검사합니다. 

preIndex = 0 이고, value = 7 > array[preIndex] = 3 이므로 while 문 내부로 들어갈 수 없습니다. 

 

array[preIndex + 1] = value; 를 실행함으로써 인덱스에 값을 넣어줍니다. 7은 정렬할 필요가 없으므로 그대로 1번 인덱스에 위치하게됩니다. 

 

7 을 정렬했으니 다음으로 2 를 정렬할 차례입니다. 다시 for 문으로 들어갑니다. curIndex = 2, preIndex = 1 이 되겠네요.

또한 value 는 2가 됩니다. 

 

 

이제 2 < 7 이므로 while 문 내부에 진입합니다. while 문 내부에는 다음 코드가 작성되어있습니다. 

 

array[preIndex + 1] = array[preIndex]; // 이전 요소의 다음 자리에 이전 값 덮어씌우기
preIndex--; // 한칸 앞으로 당기기

 

 

 

이 상태에서 preIndex = 0 이고 2 < 3 이므로 while 문 내부 코드가 한번 더 실행 됩니다. 

 

 

 

 

preIndex = -1 이므로 while 문을 빠져나갑니다. 마지막으로 다음 코드가 실행되면서 요소가 정렬됩니다.

 

array[preIndex + 1] = value;

 

 

이제 curIndex 가 1을 가리키면서 앞서 했던 로직을 반복하면 됩니다. 

 

마무리

 

오늘은 삽입 정렬에 대해 다루어보았습니다.

 

삽입 정렬을 구현하는 방법은 여러가지가 될 수 있으므로 코드를 보고 외운다는 느낌보다는 삽입 정렬이 어떤 방식의 정렬인지 이해하고 이해한 바를 코드로 먼저 작성해보는 연습을 해보시기 바랍니다.