병합 정렬(Merge sort)

▷ 합병정렬(Merge sort)

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다.

▷ 정렬방법.

1. 데이터 집합을 반으로 나눈다.

2. 데이터 집합의 크기가 2이상일 경우 하나의 원소가 될때까지 1번을 반복한다.

3. 같은 집합에서 나뉘어진 원소끼리 정렬하면서 집합으로 만든다.

4. 모든 원소가 하나의 집합이 될때까지 3번을 반복한다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

시작 : 5, 1, 6, 4, 8, 3, 7, 9, 2

※ 분할 - 파란색 블록은 기준점이다.

 

※ 정복

Code 

#include <iostream>
using namespace std;
 
#define MAX            5
 
void MergeSort(int *Number, int Low, int Mid, int High);
void Division(int *Number, int Low, int High);
void main()
{
    int Number[MAX] = {5,1,6,4,8,3,7,9,2};
 
    Division( Number, 0, MAX - 1);
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
// 분할
void Division(int *Number, int Low, int High)
{
    int Mid;
 
    if(Low < High)
    {
        Mid = (Low + High) / 2;
        Division( Number, Low, Mid );
        Division( Number, Mid + 1, High);
        MergeSort( Number, Low, Mid, High);
    }
}
 
// 정복
void MergeSort( int *Number, int Low, int Mid, int High)
{
    // 집합의 크기만큼 동적할당.
    int *TempIndex = new int[ High + 1 ];
 
    int Left = Low;            // 왼쪽 집합의 시작 값.
    int Right = Mid + 1;    // 오른쪽 집합의 시작 값.
    int CountIndex = Low;    // 
 
    // 왼쪽 집합과 오른쪽 집합의 원소 값을 비교하여 
    // 더 작은 값을 새로 동적할당하여 만든 집합에 대입한다.
    while(Left <= Mid && Right <= High)
    {
        if(Number[Left] < Number[Right])
            TempIndex[CountIndex++] = Number[Left++];
        else
            TempIndex[CountIndex++] = Number[Right++];
    }
 
    // 왼쪽 혹은 오른쪽 집합이 새로만든 집합에 모두 들어갔을 경우
    // 남은 집합을 새로운 집합에 모두 집어넣는다.
    if( Left > Mid )
    {
        for(int i = Right; i <= High; i++)
            TempIndex[CountIndex++] = Number[i];
    }
    else
    {
        for(int i = Left; i <= Mid; i++)
            TempIndex[CountIndex++] = Number[i];
    }
 
    // 새로만든 집합공간에 있는 모든 원소값을 원래 존재했던 집합 공간에 대입한다.
    for(int i = Low; i <= High; i++)
        Number[i] = TempIndex[i];
 
    // 새로 만들었던 집합공간의 메모리 해제.
    delete[] TempIndex;
}

결과