컴퓨터 알고리즘 초급 #4 ( 합병정렬 in c )

 

합병 정렬 알고리즘

 

 

합병 정렬이란?  - 합병을 이용한 알고리즘 

 

합병이란?  - 두개를 합치는 것

 

무엇을 합병할 것인가?  두개의 정렬된 배열을 하나의 배열로 합병

 

 

 

입력 : n개의 숫자

 

출력 : 정렬된 n 개의 숫자  ( 오름 차순 )

ex ) 

배열 1 : <1,5,6,8> 배열 2 : <2,4,7,9>  -> 결과 : <,1,2,4,5,6,7,8,9>

 

 

 

Point : 두 정렬은 이미 정렬이 되어 있다.

 

알고리즘 : 배열 1과 배열 2의 첫번째 숫자를 비교해서 저 작은걸 결과의 첫번째에 넣어준다. 여기서는 배열 1의 첫번째 숫자 (1) 이 더 작으므로 1을 넣는다. 그 후 더 작았던 배열 1의 첫번째 숫자를 삭제한다. 그 후 배열 1의 첫번째 자리와 배열2의 첫번째 자리를 비교하는 작업을 반복한다.

 

 

Step0 : 배열 1 : <5,6,8> 배열 2 : <2,4,7,9> -> 결과 : <1>

Step1 : 배열 1 : <5,6,8> 배열 2 : <2,4,7,9> -> 결과 : <1,2>

Step2 : 배열 1 : <5,6,8> 배열 2 : <4,7,9> -> 결과 : <1,2,4>

Step3 : 배열 1 : <5,6,8> 배열 2 : <7,9> -> 결과 : <1,2,4,5>

Step4 : 배열 1 : <6,8> 배열 2 : <7,9> -> 결과 : <1,2,4,5,6>

Step5 : 배열 1 : <8> 배열 2 : <7,9> -> 결과 : <1,2,4,5,6,7>

Step6 : 배열 1 : <8> 배열 2 : <9> -> 결과 : <1,2,4,5,6,7,8>

Step7 : 배열 1 : <> 배열 2 : <9> -> 결과 : <1,2,4,5,6,7,8,9>

 

결과적으로 모두 정렬된다.

 

합병정렬의 수행시간 ( 성능 ) : 두개의 정렬된 배열의 길이를 각 각 n1, n2라고 하면 O(n1+n2)이다.

 

두 숫자를 비교 후 새로운 배열에 이동 , 사용되는 함수는 비교함수와 이동함수가 사용된다.

 

합병정렬 알고리즘은 주어진 배열의 모든 숫자가 이동할 때 까지 이동. 각 5개의 아이템이면, 10개의 숫자가 이동해야함. 즉 n1+n2번 이동(10번)

 

비교함수는 이동마다 각 한번씩만 비교하면 되므로 n1+n2 보다 작거나 같다.

 

최고차항만 따지면

결론 : O(n1+n2)

 

 

만약 입력이 정렬된 두 입력이 아닐 경우는 어떻게 해야할까?

 

====

 

-> A divide-and-conquer approach  : 크기가 커서 한번에 풀기 어려운 문제를 크기가 작은 여러 문제로 바꾼 후 푸는 방법

 

Divide : n 개의 Key를 두 개의 n/2 Keys로 나눈다. ( 계속해서 나눌 수 있음 )

 

Conquer : 합병정렬을 사용하여 두 개의 배열을 정렬한다.

 

Combine : 두 개의 정렬된 배열을 하나로 합치는 과정

 

ex) 

 

입력 : 5, 2, 4, 7, 1, 3, 2, 6

 

divide

 

<5,2,4,7> <1,3,2,6>

 

<5,2> <4,7> <1,3> <2,6>

 

<5> <2> <4> <7> <1> <3> <2> <6>

 

n개의 입력이 들어오면 1개씩 쪼갠다.

 

다시 재결합

 

<2,5> <4,7> <1,3> <2,6>

 

<2,4,5,7> <1,2,3,6>

 

<1,2,2,3,4,5,6,7>

 

 

이는 재귀트리를 이용한 풀이의 기본 아이디어가 된다.

 

정렬되지 않은 배열이 들어올 시 수행시간 : O(nlogn)

 

 

#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;

}

//출처 : https://hongku.tistory.com/152

코드 출처 : https://hongku.tistory.com/152

자료구조 :: 병합정렬 Merge sort (c/c++ 구현)

 

2020/03/10 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #1 ( 컴퓨터 알고리즘 개요 )

2020/03/10 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #2 ( 선택정렬 in c )

2020/03/18 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #3 ( 삽입정렬 in c )