정렬(Sort) : 삽입정렬(Insertion Sort)

자료구조 정렬에 대한 첫번째 포스팅, 정렬 알고리즘에 대해 공부하고자 들어오셨다면 읽고 가시면 되는데 필요한 분이 있을것 같아서 파이썬 정렬에 대한 링크 첨부합니다.

파이썬 예제 : 리스트를 정렬(Sort)하는 여러가지 방법 : http://andrew0409.tistory.com/65

파이썬 예제 : 튜플(Tuple)을 정렬(Sort)하는 여러가지 방법 : http://andrew0409.tistory.com/66

그럼 지금부터 자료구조 정렬(Sort)에 대한 첫번째 포스팅으로 삽입정렬에 대하여 간단하게 알아보도록 하겠습니다.

아래는 삽입정렬의 알고리즘을 그림으로 표현한것

아래 동영상을 한번 참고해보실까요, 영상은 삽입정렬에 대한 알고리즘을 포크댄스로 표현한 것입니다. 이해를 돕기위하여 첨부합니다.

위 동영상을 예시로 설명을 시작하겠습니다.

최초에 정렬되지 않은 숫자들의 배열이 있습니다. 코드로 표현해보면 아래와 같이 쓸 수 있겠죠

#include <stdio.h>
#define ARRAY_SIZE 10
 
int main()
{
    int size = ARRAY_SIZE;
    int arr[ARRAY_SIZE] = { 3, 0, 1, 8, 7, 2, 5, 4, 9, 6 };
    
    return 0;
}

배열의 크기를 10으로 잡고, 그 안에 동영상에 나온 순서대로 숫자를 넣어 초기화 했습니다. 특이점은 없습니다. #define 매크로상수에 대해서는 알고 오셨으리라 생각하고, 설명을 생략하겠습니다. 이는 별도의 포스팅에서 다루어 보도록 하겠습니다.

3

0

1

8

7

2

5

4

9

6

최초 정의된 배열의 상태는 위와 같습니다. 이제 삽입 정렬을 통해서 순서대로 정렬해볼 텐데요.

영상을 보고 느끼셨을지 모르겠지만, 배열은 크게 두가지 영역으로 나눌 수 있습니다. 하나는 이미 정렬된 영역, 하나는 아직 정렬되지 않은 영역.

그럼 최초 정의된 배열에서 정렬된 부분은 어디일까요?

3

0

1

8

7

2

5

4

9

6

바로 가장 첫번째 방 입니다. 첫번째 방을 제외하고는 아무것도 정렬되지 않은 상태라고 생각하면 됩니다. 첫번째 방에서부터 한칸씩 옆으로 가면서 정렬하면 됩니다. 쭉쭉 달려보겠습니다.

0

3

1

8

7

2

5

4

9

6

첫번째 방과 두번째 방을 비교하여 서로 자리를 바꾼 상태

0

1

3

8

7

2

5

4

9

6

두번째 방과 세번째 방을 비교하여 자리를 바꾼 상태

0

1

3

8

7

2

5

4

9

6

세번째 방과 네번째 방을 비교했지만 이상이 없어서 그대로 둔 상태, 이렇게 정렬된 영역을 하나씩 늘려갑니다.

0

1

3

7

8

2

5

4

9

6

마찬가지로 7과 8을 비교하여 자리를 바꾸었죠. 어떤 느낌인지 감을 잡으셨으리라 생각합니다. 뒤에있는 2는 어떻게 비교할까요? 우선 8과 비교하여 두개의 자리를 바꾸고, 다시 7과 비교하여 자리를 바꾸고, 3과비교하여 자리를 바꾼 후 1과 비교한 뒤 자리를 잡게됩니다. 이제 이를 코드로 표현해보겠습니다.

void insertion(int *p, int size)
{
    int i, save = p[size - 1];
 
    for (i = size - 2; i >= 0; i--)
    {
        if (p[i] <= save)
            break;
        p[i + 1] = p[i];
    }
 
    p[i + 1] = save;
}

    for (int i = 2; i <= size; i++)
        insertion(arr, i);

위와같이 insertion 함수를 정의하고, 아래와같이 반복문을 이용하여 사용하였습니다. 코드를 흐름에 따라 하나씩 살펴보도록 하겠습니다. 일단 이름에서도 알 수 있듯이 insertion 함수가 삽입정렬에서의 삽입을 담당하고 있다고 치고, 아래 반복문을 먼저 살펴보도록 하겠습니다.

양쪽 코드를 잘 살펴보면 아시겠지만 아래 for문에서 선언된 i 변수가 insertion 함수에서는 size 변수로 전달되는것을 알 수있습니다. 그런데 i가 2부터 시작하죠. 이는 비교할 방의 개수가 2개라고 이해하시면 되겠습니다. 여기에서 한가지 짚고갈 기본 개념은 "배열의 이름은 곧 그 배열의 시작주소 상수 값" 따라서 arr 배열의 이름만 전달인자로 사용했다는 점은 arr[0]의 한차원 높은 주소값인 int의 포인터형 되겠습니다.

insertion 함수를 보시면 설명드린대로 첫번째 전달인자를 int 포인터형으로 받고, 두번째 전달인자를 int형 size라는 이름으로 받습니다. 처음에는 배열의 첫번째 방과 두번째 방, p[0]과 p[1]의 숫자의 크기를 비교 하겠죠. 그 전에 p[1]에 저장된 숫자를 save라는 변수에 미리 저장해놓습니다. i는 save가 저장되어있던 방의 주소(p[1]) 보다 한칸 앞(p[0])에서 부터 시작합니다. 그리고 루프를 돌면서 p[i] 가 save에 저장된 숫자보다 작거나 같은 순간을 찾습니다. 처음 0번방에는 3이 1번방에는 0이 들어있으니 연산의 결과는 false가 되겠죠. 따라서 반복문에서 break 하지 못하고 p[i + 1] 번방 i가 0이니 즉 p[1]번방이 되겠죠. 이곳에 p[0]번방에 저장되어있는 3을 넣습니다. 그리고 i가 디크리먼트 연산자에 의해 작아지면서 i >= 0의 연산결과에서 false가 되어 반복문을 빠져나오겠죠. 마지막으로 save에 저장되어있던 0을 p[0]에 넣습니다. 3과 0의 자리가 성공적으로 바뀌었습니다.

눈치가 빠른분은 느끼셨겠지만 반복문에서 i는 0에서 시작되면서 인크리먼트 되는 형식이 아니라 size -2 (왜냐하면 배열은 0번방부터 시작하기 때문에 10개의 방이 있을때 실제 마지막 방은 arr[9] 라고 사용한다) 부터 시작해 0까지 하나씩 디크리먼트가 되는 형식입니다. 이는 배열을 한칸씩 옆으로 밀어냄을 뜻합니다. 표를 통해 예제를 다시 보겠습니다.

0

1

3

7

8

2

5

4

9

6

여기서 insertion을 위의 코드와 같이 실행하면, save는 2가 되겠죠. 그 상태에서 2보다 작거나 같은 숫자를 찾을때까지 루프를 돌며 한칸씩 옆으로 밀어버립니다.

0

1

3

7

8

5

4

9

6

이렇게 말이죠. 그리고 이렇게 한칸씩 밀린 상태에서 save라는 임시변수에 저장되어있던 2를 빈 자리에 삽입합니다. 이것이 삽입정렬이라는 이름의 이유입니다. 빈칸을 찾아 한개씩 삽입한다는 뜻입니다. 

코드의 흐름에 따라 정렬이 진행되는 모습을 살펴보려고 했는데 적다보니 불필요하게 설명이 길게되어 글이 어수선합니다. 잘 이해가 안되는 부분은 질문 해주시면 되겠고요, 지적도 달게 받겠습니다. 추천이나 댓글은 큰 힘이 됩니다. 정렬(Sort) : 삽입정렬(Insertion Sort) 편을 마치겠습니다. 내일은 선택정렬(Selection Sort)에 대해서 다루어 보겠습니다. 감사합니다.

아래는 최종 코드입니다.

버전1.

#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 10
 
void insertion(int *p, int size);
 
int main()
{
    int size = ARRAY_SIZE;
    int arr[ARRAY_SIZE] = { 3, 0, 1, 8, 7, 2, 5, 4, 9, 6 };
    
    //for (int i = 0; i < size; i++)
    //    arr[i] = rand() % size+10; //배열을 랜덤한값으로 초기화 시켜준다.
 
    for (int i = 2; i <= size; i++)
        insertion(arr, i);
    
 
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}
 
void insertion(int *p, int size)
{
    int i, save = p[size - 1];
 
    for (i = size - 2; i >= 0; i--)
    {
        if (p[i] <= save)
            break;
        p[i + 1] = p[i];
    }
 
    p[i + 1] = save;
}
 

버전2.

#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 10
 
void insertNextItem(int a[], int i);
void insertionSort(int a[], int n);
 
int main()
{
    int size = ARRAY_SIZE;
    int arr[10];
 
    for (int i = 0; i < size; i++)
        arr[i] = rand() % size + 10;
 
    insertionSort(arr, size);
 
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}
 
void insertionSort(int arr[], int size)
{
    for (int i = 1; i < size; i++)
        insertNextItem(arr, i);
}
 
void insertNextItem(int arr[], int i)
{
    int newItem(arr[i]), insertPos(i);
    for (; insertPos && newItem < arr[insertPos - 1]; insertPos--)
        arr[insertPos] = arr[insertPos - 1];
    arr[insertPos] = newItem;
}

버전 2의 경우 제가 학교에서 수강하는 자료구조 과목의 강의노트에서 가져왔습니다. 참고하셔서 공부의 도움이 되었으면 좋겠습니다. (어느것으로 사용해도 상관 없습니다.)