전북대학교 알고리즘 합병정렬 5조 안준철

합병정렬은

    - 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함.

    - 합병 정렬은 퀵정렬과 마찬가지로 분할 정복 방식의 알고리즘이다.

    - 두 부분의 배열의 크기가 동일 해야 한다.

성능분석

    - 최악의 경우에도 N개의 원소를 가진 화일을 정렬하는데 N logN에 비례하는 시간이 걸린다.

    - 순차적 방식에 의해 데이터를 접근한다.

    - 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우만 사용 가능 하다.

    - N에 비례하는 추가 기억 장소가 필요하다.

    - 안정적이지만 제자리 정렬은 아니다.

알고리즘분석

합병 정렬의 기본 아이디어는 3단계로 요약된다.
정렬될 리스트 List = ( 6 ,2 ,8 ,1 ,3 ,9 ,4 ,5 ,10 ,7 ) 가 있다고 가정하자.

 1. 이 리스트 A를 이등분하여 L={6,2,8,1,3}, R={9,4,5,10,7} 로 만든다.

2. 리스트 L과 R을 정렬한다. L={1,2,3,6,8} , R={4,5,7,9,10}

3. 이두리스트 L과 R을 합병하여 정렬 리스트를 만든다. { 1,2,3,4,5,6,7,8,9,10 }

합병 정렬 알고리즘 ADT

MergeSort(a[], l ,r)

    if (r>l) then {

     m <-  (r+1) / 2 ;

     MergeSort(a[],l,m);

     MergeSort(a[],m+1,r);

     Merge(a[],l,m,r);

}

end MergeSort()

소스 코드

#include <iostream.h>
#include <time.h>
#include <stdlib.h>

const int N = 10000;
int b[N+1];

void MergeSort(int a[], int l, int r)
{
    int i,j,k,m;

    if(r>l)
    {
        m = (r+l) / 2;
        MergeSort(a,l,m);
        MergeSort(a,m+1,r);

        for(i=m+1;i>l;i--) b[i-1] = a[i-1];
        for(j=m;j<r;j++) b[r+m-j] = a[j+1];
        for(k=l;k<=r;k++)
         a[k] = (b[i] < b[j]) ? b[i++] : b[j--];
    }
}

main()
{
    int i,a[N+1];
    double start_time;  

    srand(time(NULL));

    for(i=1;i<=N;i++) a[i] = rand();

    start_time = clock();
    MergeSort(a,1,N);
    cout << "합병 정렬의 실행 시간 (N=" << N << ") :  " << clock()-start_time << endl

출처:

http://alg.devlife.net/MergeSort/MergeSort.aspx
http://alg.devlife.net/MergeSort/MergeSort.aspx
http://alg.devlife.net/MergeSort/MergeSort.aspx

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

• 전북대학교 알고리즘 합병정렬 5조 - 알고리즘 & 자료구조 by prettyhip