#003_자료구조와 알고리즘_삽입 정렬

안녕하세요 삽잡이입니다.

이번 시간에는 

지난 시간, 버블 정렬과 선택 정렬에 이은 삽입 정렬에 대해서 알아보려고 합니다.

삽입 정렬은 배열의 부분 배열을 정렬 시켜 나가는 정렬 방식입니다.

예를 들어보도록 하겠습니다. 삽잡이가 '원카드' 게임을 한다고 가정해보죠... 

해당 게임에 사용하는 카드는 다이아, 하트, 스페이드, 클로버 모양과 각각 순서에 맞는 카드를 제공해줍니다.

카드를 뒤섞어 놓고 상대와 본인은 한장씩 뒤집힌 카드를 가져갑니다.

왼손에 한장씩 카드를 가져오는데 

평소 조그마한 정리 조차 하지 않으면 미칠듯이 불안감에 빠지는 삽잡이는

한장, 한장 카드를 집어 왼손으로 가져올 때마다

카드를 순서대로 정리합니다...

그리고 정해진 수의 카드를 가져갔다면, 이제 게임은 시작 됩니다.

이게 삽입 정렬입니다. 뭔말이냐구요? 

뽑은 카드를 어디에 집어 넣을지에 대해 찾는 정렬이라구요~!

코드를 살펴보도록 하겠습니다.

//header
#pragma once
 
template <typename Element, typename Compare>
void insertion_sort(Element *base, int n, Compare compare)
{
    for (int i = 1; i<n; i++)
    {
        for (int j = i; j>0; j--)
        {
            if (compare(base[j - 1], base[j])>0)
            {
                Element temp = base[j - 1];
                base[j - 1] = base[j];
                base[j] = temp;
            }
            else
            {
                break;
            }
        }
    }
}

가장 바깥을 감싸고 있는 Loop 문은 

카드를 가져오는 횟수라고 생각해 보도록 하겠습니다.

한장 한장 가져올 때마다 당연하게도 카드의 수는 증가하게 되고, 

가져와야 할 개수는 그만큼 줄어들게 되죠...

안쪽에 감싸고 있는 Loop문은

집어온 카드를 이전에 소유하고 있는 카드들과 비교를 하여

크기가 작은 카드 부터 정렬 시키기 위한 행위를 표현한 것입니다.

카드를 가져올 때마다 크기를 맞추는... 

예전에 수학여행 가서 게임할 때를 생각해보세요... 

꼭 실력 상관없이 가져오는 카드마냥 족족 순서대로 정리하는 사람들 꼭 있습니다. 

물론 저를 포함해서 말입니다...

그럼 이제 이 선택 정렬을 사용한 소스 파일을 보여드리고 글을 마치겠습니다.

//cpp 파일
#define MAX 100
int CompareInt(int a,int b)
{
    return a-b;
}
 
void TestInsertionSort()
{
    int *arr = new int[MAX];
    for (int i = 0; i < MAX; i++)
    {
        arr[i] = rand() % 1000;
    }
 
    insertion_sort(arr, MAX, CompareInt);
 
    for (int i = 0; i < MAX; i++)
    {
        cout << arr[i] << " ";
        if ((i + 1) % 10 == 0)
        {
            cout << endl;
        }
    }
    cout << "----------------" << endl;
 
}
 
void main()
{
    TestInsertionSort();
}

기존에 정렬이 되어 있는 상태에서 추후 들어올 데이터들이 정렬이 되어있지 않는다면...? 

이때에 삽입 정렬을 사용한다면 효과적이라고 하네요...

이상 삽잡이였습니다~!