병합정렬 (Merge Sort)

기본 개념

병합 정렬을 알기 전에 우선 Devide and Conquer에 관한 개념을 알고 있어야 합니다. 아니, 몰라도 됩니다. 이제부터 배울꺼거든요. 간단히 말해 어떤 문제를 우선 작은 문제로 쪼개고 난 후 다시 조합하여 원래의 문제를 푼다는 것인데요.

병합정렬을 통해서 어떤 개념인지 알아보도록 하겠습니다.

우선 배열이 있습니다. 정렬이 되지 않은 정수형 배열이지요.

일단 묻지도 따지지도 않고 쪼갭니다. 아주 산산조각을 냅니다.

이 후에 쪼갠 역순으로 정렬을 하는 것입니다. 아래의 그림처럼요. 쪼갠것을 다시 차근차근 조립하면서 정렬하는 것을 볼 수 있지요.

그래서 우리는 이 그림을 이해하는 것이 목적입니다.

구현

구현은 2가지의 큰 틀로 구성이 됩니다.

1. 분할

가장 먼저 해야될 작업입니다. 이 작업은 쉽습니다. 배열을 그냥 2로 계속 나누다보면 언젠가는 하나의 원소를 갖게되니까 그때 멈추면 됩니다. 

mergeSort라는 함수를  보세요. 정렬할 배열과 왼쪽끝을 나타내는 left, 오른쪽 끝을 나타내는 right를 인자로 받고 있습니다.

void mergeSort(int arr[], int left, int right) {

	if(left==right) return;  
	int mid;
	
	mid = (left + right) / 2;
	mergeSort(arr, left, mid); 
	mergeSort(arr, mid + 1, right); 
	
}

아래의 그림처럼 left와 right를 이용해서 mid를 기준으로 쪼개는 겁니다. mid는 left와 right의 중간 부분을 가리키고 있죠. 

그러다가 하나의 원소만 남게되면 바로 return이 됩니다. 어떻게 알 수 있을까요? 하나의 원소만 남았다는 것은 left와 right가 서로 같은 값을 가졌다는 것을 의미하니까 left==right라면 바로 return 하면 됩니다.

2. 병합

병합은 조금 어려울 수도 있지만 이해하면 별거 없습니다. 

우선 코드부터 보면서 이해하자구요.

void merge(int arr[], int left, int right) {
	
	int L, R, k, a;
	int mid = ( left + right ) / 2;
	L = left;
	R = mid + 1;
	k = left;

	while (L <= mid && R <= right)
		tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];

	if (L>mid) 
		for (a = R; a <= right; a++)
			tmp[k++] = arr[a];
	else 
		for (a = L; a <= mid; a++)
			tmp[k++] = arr[a];
	
	for (a = left; a <= right; a++) 
		arr[a] = tmp[a];
	
}

뭐지 이 변태같은 코드는? 이러지 마시구요. 하나하나 보도록 합시다. 차근차근히

인자로 배열 arr과 left, right를 받고 있습니다. 나누어진 배열의 한쪽은 L, 그리고 다른 한쪽은 R을 인덱스로 하기로 합시다. 쪼개진 배열 하나를 왼쪽에 있다 생각하고 L, 다른 하나는 오른쪽에 있다고 생각하고 R로 한거에요. R은 mid+1부터 시작해야겠죠? 

tmp라는 임시배열은 k를 인덱스로 합니다.

그리고 나누어 쪼개져서 정렬된 일부분의 배열을 부분 배열이라고 하겠습니다. 

자, 됐으면 이제 while문을 돕니다. while루프는 왼쪽 부분 배열을 전부 다 돌았거나 오른쪽 부분 배열을 전부다 돌때까지 반복합니다. 그러니 L은 mid 이하까지 R은 right 이하까지 반복하는데 왼쪽 배열, 오른쪽 배열 하나라도 전부 반복이 되었다면 탈출합니다. 

여기서부터는 그림이 좀 필요하겠네요.

왼쪽 부분 배열과 오른쪽 부분 배열의 원소를 비교해서 더 작은 값이 tmp로 값이 복사됩니다. 같을 때는 아무거나 넣어도 상관없겠죠. 그러니 현재 1과 2 중 1이 더 작으므로 tmp에 1이 저장됩니다. 그리고 L과 k를 하나씩 증가시키죠. 사실 k는 계속 증가하는 상태입니다. 항상 값이 들어가니까요.

그 후 arr[L]과 arr[R] 중 값이 작은 것을 또 선택합니다. 3과 2 중 2가 더 작으니 2를 tmp에 넣습니다. 이후 R과 k는 증가합니다. 

마찬가지입니다. arr[L]과 arr[R] 중 가장 작은 값은 3이므로 3을 넣습니다. 그 후 k와 L의 값이 하나 증가합니다.

4까지 넣고 나면 한쪽 부분 배열(왼쪽)이 전부 tmp에 저장됐으므로 이제 while루프는 종료됩니다. 

이제 남은 것을 옮겨야하는데요. 5가 남았죠? 

만약 L이 mid보다 크다면 왼쪽 부분 배열이 tmp에 전부 복사된 것이므로 오른쪽에 있는 부분 배열의 값을 모조리 tmp에 집어넣습니다. 

반대도 역시 똑같습니다. 오른쪽 부분 배열이 전부 tmp에 복사되었다면 R은 right보다 크게 될테니까 왼쪽 부분 배열의 남은 값을 전부 tmp에 집어넣으면 되는 것이죠.

이제 원본 배열에 값을 다시 돌려주어야합니다. tmp는 잠시 저장하는 용도로 쓰기 때문이죠.

어때요. 아름답게 정렬이 된것을 확인할 수 있죠??

merge라는 함수를 구현했으니, 이제 mergeSort에서도 이 함수를 이용해서 병합! 하면 됩니다. 아래처럼 merge 함수를 추가하세요. 

void mergeSort(int arr[], int left, int right) {
	
	if (left == right) return;
	int mid;
	mid = (left + right) / 2;
	mergeSort(arr, left, mid); 
	mergeSort(arr, mid + 1, right); 
	merge(arr, left, right); 
	
}

보다 이해가 잘 되기 위해 전체코드를 보세요.

#include <stdio.h>
#define SIZE 5
int tmp[SIZE];
					
void merge(int arr[], int left, int right) {
	
	int L, R, k, a;
	int mid = (left + right) / 2;
	L = left;
	R = mid + 1;
	k = left;

	while (L <= mid && R <= right)
		tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];

	if (L>mid) 
		for (a = R; a <= right; a++)
			tmp[k++] = arr[a];
	else 
		for (a = L; a <= mid; a++)
			tmp[k++] = arr[a];
	
	for (a = left; a <= right; a++) 
		arr[a] = tmp[a];
	
}


void mergeSort(int arr[], int left, int right) {
	
	if (left == right) return;
	int mid;
	mid = (left + right) / 2;
	mergeSort(arr, left, mid); 
	mergeSort(arr, mid + 1, right); 
	merge(arr, left, right); 
	
}
void printArr(int arr[], int size) {
	int i;
	for (i = 0; i<size; i++) 
		printf("%d ", arr[i]);
	
	printf("\n");
}
void main() {
	int i;
	int arr[SIZE] = { 3,4,1,5,2 };

	mergeSort(arr, 0, SIZE - 1);
	printArr(arr, SIZE);
}

시간복잡도

버블 정렬이나 선택정렬 이런 정렬과는 어떤 차이가 있을까요?? 시간복잡도에서 차이가 있습니다. 병합정렬은 nlogn의 시간복잡도를 갖고 있습니다. 계속 둘로 쪼갠 횟수 만큼 n번의 루프를 돌기 때문입니다. 더 빠르다는 것을 알 수 있습니다.

정렬 알고리즘

정렬 알고리즘은 알고리즘 과목 중에서 기초적으로 반드시 알고 지나가야되는 파트입니다. 단순히 작은 순, 또는 큰 순으로 순서를 정렬하는 데에도 여러가지 알고리즘이 존재하는데요. 우리가 바로바로 이해할 수 있는 알고리즘이 있는 가 하면 좀 복잡하게 정렬하는 알고리즘도 있지요. 우리는 그나마 쉬운 편에 속하는 정렬 알고리즘 3개를 같이 보겠습니다.

1. 선택정렬(Selection Sort)

선택 정렬은 일단 자리는 정해져있습니다. 첫번째 자리에 가장 작은 녀석을 집어넣으면 되죠. 그리고 난 후에 두번째 자리에 그 다음 가장 작은 녀석을 선택해 집어 넣습니다. 이 짓을 배열이 끝날때까지 합니다.

다음 배열 arr에는 9, 8, 1, 2, 3이 있습니다. 이것을 선택정렬로 정렬하도록 해봅시다.

우선 제일 첫번째 자리 , 즉 9가 있는 자리를 i라고 놓고 j는 i 다음부터 배열의 가장 작은 index를 뽑아 옵니다. 그것을 minIndex라고 하지요.

j는 8부터 배열을 검색하면서 가장 작은 index를 찾아보니 1이 있는 자리가 제일 작군요. 그러니 minIndex는 2(1이 있는 배열 원소의 위치!)가 됩니다. 그래서 가장 첫번째 자리는 1이 되겠습니다.

그 후 두번째 자리(8이 있는 자리)가 i가 되고, j는 그다음 가장 작은 원소의 index를 구하게 되니까 minIndex는 2가 있는 자리, 즉 4가 됩니다.

minIndex와 i를 바꿉니다.

다음은 9가 있는 자리입니다. i는 2가 되겠네요. 가장 작은 인덱스는 3이 있는 자리이므로 i와 바꾸어 줍니다.

다음 i가 하나 증가되어 9를 가리킵니다. 8이 더 작으니까 바꾸어 주어야겠죠??

이제 모든 비교와 교환은 끝났습니다. 오름차순으로 정렬이 된것을 볼 수 있습니다.

아래는 선택정렬을 구현한 코드입니다.

void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(&arr[i], &arr[minIndex]);
    }
}

인덱스를 j라고 표시하겠습니다. 우선 가장 앞 자리부터 그 다음 원소를 비교합니다. 9와 8을 우선 비교하는 것이죠. 9가 더 크니 8과 9를 바꿉시다. 

그 다음 j가 하나 증가하여 다음 자리를 가리키고 9와 1을 비교합니다. 9가 더 크니 1과 9를 바꿉시다.

느낌 오시나요? 가장 큰 요소를 끝으로 보내려고 하는 겁니다. 다음 j를 하나 증가시키고 9와 3을 비교합니다. 9가 더크네요. 3과 9를 바꾸어줍니다.

다시 j가 하나 증가하게 되고 9과 2를 비교해보니 9가 더 크니까 자리를 바꾸어줍니다.

이렇게 보니까 9(제일 큰 수)가 제일 뒤로 갔군요. 

그 다음은 4번째(인덱스 3)까지 이런 방식을 반복합니다. 하나씩 줄여가면서 이런 방식을 반복하여 가장 큰수를 오른쪽으로 보내면 정렬이 되는 것이죠. 버블 정렬을 코드로 구현한 것이 아래에 있습니다.

void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

삽입 정렬을 우선 배열의 한 원소인 key라는 값을 우선 가지고 있고, 이 key를 알맞은 자리에 삽입하면 됩니다. key보다 큰 값은 하나하니씩 밀어버리고 key보다 작은 값을 만났으때 그 뒷자리에 삽입하는 것입니다.

그림을 통해봅시다.

우선 배열이 이렇게 있구요. 사실 계속 이 배열을 썼었죠.

우선 key값은 배열 인덱스 1번부터 시작입니다. i 이전의 원소를 비교해야하는데, 인덱스가 0이면 비교할게 없으니까요. key는 8로 8보다 큰 값은 오른쪽으로 밀어버립니다. 8보다 작은 원소가 발견되면 그 원소 뒤에 8을 삽입해야하는 데 없으므로 제일 앞에 삽입합니다.

8이 맨앞에 삽입 되고 난 후 i가 하나 증가하여 계속 비교합니다. key는 1이 됩니다. 1보다 작은 원소가 없으므로 제일 앞에 위치하게 됩니다.

이후 i가 하나 증가하고 키는 3입니다. 3보다 작은 원소를 만날때 그 뒤에 삽입하는 과정을 아래 그림이 보여줍니다.

이제 i가 하나 증가하게 되고 마지막 원소인 2가 키가 됩니다. 2보다 작은 원소는 1이므로 1뒤에 2를 삽입하는 것이 되지요. 아래 그림이 그 과정을 보여줍니다.

최종적으로 정렬된 상태는 바로 이와 같습니다.

삽입 정렬에 대한 코드는 아래와 같습니다.

void insertionSort(int arr[], int size) {
    int i, j, key;

    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

시간복잡도

선택 정렬과 버블 정렬은 항상 n^2의 시간복잡도를 갖지만 삽입정렬은 조금 다릅니다. 삽입 정렬은 평균적으로 n^2이지만 만약 정렬된 원소들로 구성된 배열이 입력으로 들어오면 n^2의 시간 복잡도를 갖습니다. for 루프안의 반복문이 1회만 실시하고 말거든요. 바로 현재 키보다 작은 원소를 만나기 때문입니다. 아래의 표로 쉽게 확인해보세요.

전체코드

확인하기 쉽도록 전체코드를 올립니다.

#include <stdio.h>

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(&arr[i], &arr[minIndex]);
    }
}
void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

void insertionSort(int arr[], int size) {
    int i, j, key;

    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}


void printArr(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr1[] = { 9,8,1,3,2 };
    int arr2[] = { 9,8,1,3,2 };
    int arr3[] = { 9,8,1,3,2 };
    int size = 5;
    printArr(arr1, size);
    selectionSort(arr1, size);
    printArr(arr1, size);
    printf("\n");

    printArr(arr2, size);
    bubbleSort(arr2, size);
    printArr(arr2, size);
    printf("\n");

    printArr(arr3, size);
    insertionSort(arr3, size);
    printArr(arr3, size);

    return 0;
}

정렬 알고리즘에는 이 밖에도 병합정렬, 퀵정렬, 힙정렬 등이 있습니다. 일단 이것부터숙지하도록 합시다.

트리

트리는 비선형 자료구조로 노드로 구성되어 있습니다. 노드들이 링크(선)를 통해 연결되어 있으며 계층적 구조를 나타내고자 할때 사용됩니다.

아래의 트리 그림을 가지고 하나하나 기본적인 설명을 하도록 하겠습니다.

⊙루트노드 (root) : 트리의 가장 위, 즉 최상위 노드를 말합니다. 트리에서 가장 중요한 노드입니다. 여기서 A가 루트노드입니다.

⊙잎 또는 단말 노드 (leaf) : 트리의 가장 끝자락에 위치한 노드입니다. 위 트리에서는 G, H, E, I, J가 해당됩니다.

⊙부모노드 (parent) : 현재노드의 한단계 위 계층에 있는 노드를 말합니다. I의 부모노드는 F, C의 부모노드는 A입니다. 

⊙형제노드 (sibling) : 부모가 같은 노드를 의미합니다. D의 형제노드는 E, G의 형제노드는 H입니다.

트리 순회

트리에는 크게 세가지의 순회 방법이 있습니다. 그 노드를 어떤 순서로 방문하느냐에 따라서 달라집니다. 그 전에 트리를 구현하는 방법을 알아보아야겠죠?

노드가 어떤 식으로 구성되어 있는 지 잠깐만 살펴보겠습니다.

typedef struct node {
	char data;
	struct node *left;
	struct node *right;
} Node;

각 노드는 data라는 변수를 갖고 있습니다. 이 data의 변수는 위 그림에서 알파벳을 저정하고 있습니다.

그리고 left는 그 노드의 왼쪽 자식 노드, right는 그 노드의 오른쪽 자식노드를 의미합니다. 가장 끝에 있는 노드는 left와 right가 NULL이라는 점입니다.

위 트리를 3가지 순회방법인 전위순회, 후위순회, 중위순회 순으로 탐색해봅시다

전위순회(preorder traversal)

전위순회는 현재 노드를 가장 먼저 방문합니다. 그러니 왼쪽 자식과 오른쪽 자식을 현재 자식보다 나중에 방문합니다.

위 그래프를 전위순회로 방문하게 된다면 

A -> B -> D -> G -> H -> E -> C ->F ->I -> J

순으로 트리가 방문됩니다.

void preorder(Node *node) {
	if (node == NULL) return;
	printf(" %c ", node->data);
	preorder(node->left);
	preorder(node->right);
}

후위순회(postorder traversal)

이름에서부터 짐작하셨겠지만 현재 노드를 가장 나중에 방문하는 방식의 순회입니다. 그러니 왼쪽 자식, 오른쪽 자식 노드를 우선적으로 방문합니다.

그러니 후위순회의 결과는

G -> H -> D -> E -> B ->I -> J -> F -> C -> A

입니다.

void postorder(Node *node) {
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	printf(" %c ", node->data);
}

중위순회(inorder traversal)

우선 왼쪽 자식을 방문하고, 현재 노드를 방문합니다. 그리고 나서 오른쪽 자식 노드를 방문하게 됩니다. 현재 노드를 중간에 방문한다고 해서 중위순회가 됩니다.

방문 순서는 이렇습니다.

G -> D -> H -> B -> E -> A -> C ->I -> F -> J

void inorder(Node *node) {
	if (node == NULL) return;
	inorder(node->left);
	printf(" %c ", node->data);
	inorder(node->right);
}

전체코드

전체코드는 아래와 같습니다. 위의 트리를 그대로 코드로 옮긴거죠. 입력받으면서 동적으로 할 수도 있겠지만 그런 귀찮은 부분까지는 고려하지 않았습니다. 여러분들이 더 잘하실테니까요.

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
	char data;
	struct node *left;
	struct node *right;
} Node;

Node *createNode(char data) {
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}
void preorder(Node *node) {
	if (node == NULL) return;
	printf(" %c ", node->data);
	preorder(node->left);
	preorder(node->right);
}

void postorder(Node *node) {
	if (node == NULL) return;
	postorder(node->left);
	postorder(node->right);
	printf(" %c ", node->data);
}

void inorder(Node *node) {
	if (node == NULL) return;
	inorder(node->left);
	printf(" %c ", node->data);
	inorder(node->right);
}


int main() {
	Node *A = createNode('A');
	Node *B = createNode('B');
	Node *C = createNode('C');
	Node *D = createNode('D');
	Node *E = createNode('E');
	Node *F = createNode('F');
	Node *G = createNode('G');
	Node *H = createNode('H');
	Node *I = createNode('I');
	Node *J = createNode('J');
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	D->left = G;
	D->right = H;
	C->right = F;
	F->left = I;
	F->right = J;


	printf("전위 순회: ");
	preorder(A);
	printf("\n");

	printf("후위 순회: ");
	postorder(A);
	printf("\n");

	printf("중위 순회: ");
	inorder(A);
	printf("\n");

	return 0;
}