[Algorithm] 병합정렬 O(N*LogN)

앞선 포스팅 3개에서 버블정렬, 삽입정렬, 선택정렬에 대해서 알아보았습니다. 하지만 위의 3정렬방법은 굉장히 기초적인 정렬방법으로 시간복잡도는 O(N^2)를가지며 실무에서 잘 쓰이는 정렬방법은 아닙니다. 이번 포스팅부터는 시간복잡도 O(N * LogN)을 가지는 정렬방법에 대해 알아보겠습니다. 

 

먼저 이번포스팅에서는 병합정렬에 대해 알려드리겠습니다. 병합정렬은 정렬할 배열을 반으로 나누어 좌측과 우측 배열을 계속하여 분할해 나간 후 각 배열내에서 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘입니다.

 

병합정렬(합병정렬) 

그림을 통해 설명해드리겠습니다.

 

①분할과정

먼저 정렬할 숫자들을 원소단위로 분할합니다.

 

 

 

②병합과정

그런 뒤 분할한 원소들을 합치면서 정렬합니다.

 

 

병합정렬 소스 코드 (C언어/C++)

#include <stdio.h>
#include <stdlib.h>

void merge(int low, int mid, int high);
void mergeSort(int low, int high);
void printArr(int a[], int n);
void copyArray(int start, int end);

//배열크기
#define number 100000
// 빈 배열 
static int mergeArr1[number];
// 정렬되지 않은 배열 
static int mergeArr2[number];

// 합병정렬함수 
void mergeSort(int low, int high) {
    int mid;
    if(low < high) {
        mid = (low + high)/2;
        mergeSort(low, mid);
        mergeSort(mid+1, high);
        merge(low, mid, high);
	}
}

void merge(int low, int mid, int high) {

    int i = low;
    int j = mid+1;
    int k = low;

    while (i<=mid && j<=high) {
        if(mergeArr2[i] < mergeArr2[j]) {
           mergeArr1[k++] = mergeArr2[i++];
        } else if(mergeArr2[i] >= mergeArr2[j]) {
           mergeArr1[k++] = mergeArr2[j++];
        }
    }

 

    // 남은 영역 조사후 mergedArr으로 복사

    if(i>=mid) {
        while(j<=high) {
           mergeArr1[k++] = mergeArr2[j++];
        }
    }

    if(j>=high) {
        while(i<=mid) {
           mergeArr1[k++] = mergeArr2[i++];
        }
    }
    copyArray(low, high);
}

 

// 배열 출력 함수 

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

 

void copyArray(int start, int end) {
    int i;
    for (i=start; i<=end; i++) {
        mergeArr2[i] = mergeArr1[i];
    }
}

 

int main(int argc, char *argv[]) {

    int i,n;
	 
    printf("몇개의 숫자로 정렬하시겠습니까?\n");
    scanf("%d",&n);

    for(i = 0 ; i < n ; i++)
	mergeArr2[i]=rand()%1000;
  
    printf("정렬전 배열 : ");
    printArr(mergeArr2,n);

    mergeSort(0, n-1);

    printf("정렬후 배열 : ");
    printArr(mergeArr2,n); 

    system("PAUSE");

    return 0;
}

 

결과

 

[C언어] 버블정렬 (배열에 있는 정수값 오름차순 정렬하기)

[C언어] 선택정렬 (배열에 있는 정수값 내림차순 정렬하기)

[C언어] 삽입정렬 (배열에 있는 알파벳 차례대로 정렬하기)

[C언어] 퀵정렬 (가장 빠르고 효율적인 정렬방법)

[C언어] 여러가지 정렬 속도 비교(정렬의 시간복잡도