[c++] 알고리즘 - 합병 정렬 개선

자연 합병 정렬 (Natural Merge Sort)

- 주어진 배열 속에 이미 순서에 맞는 원소로 된 부분 배열, 즉 런(Run)만을 합병.

- 두 개의 런이 결정되면 합병이 수행된다. 예를 들어 배열 [6, 7, 8, 3, 4, 1, 11, 12, 13, 2]에서 런 [6, 7, 8]과 런 [3, 4]가 먼저 합병되면 [3, 4, 6, 7, 8]이 되고 런 [1, 11, 12, 13]과 런 [2]가 합병되면 [1, 2, 11, 12, 13]이 된다. 마지막으로 런 [3, 4, 6, 7, 8]과 [1, 2, 11, 12, 13]이 합병되면 [1, 2, 3, 4, 6, 7, 8, 11, 12, 13]이 된다.

 

 

 

 

 

소스 코드

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

using namespace std;
const int N = 10000;

const int TRUE = 1;
const int FALSE = 0;

void printList(int a[])
{
 int i;
 for (i = 1; i < N; i++)
   cout << a[i] << ", ";

 cout << a[i] << endl;
}

void CheckTime(int a[], int n)
{
  int i, Sorted;
  Sorted = TRUE;
  for (i = 1; i < n; i++) {
    if (a[i] > a[i+1]) Sorted = FALSE;
    if (!Sorted) break;
  }
  if (Sorted) cout << "정렬 완료." << endl;
  else cout << "정렬 오류 발생." << endl;
}

void NaturalMergeSort(int a[], int l, int r)
{
 int i, j, k, m;
 int tempNum=0; //tempNum - 동적배열에 얼만큼 잡혀있는지 알려줌 --묶음의 갯수
 int p1=0, p2=0; //묶음별 피봇
 int position; //옮길 배열 위치
 int cnt1, cnt2;// 각 묶음당 원소 갯수
 int wall; //두 묶음 합병한 원소수
 int count=1; //루프를 끝내기 위한 변수
 int flag = 0; //위의 count 변수를 사용하기위한 조건
 int b[N+1];
 int tempArray[N]={0,};
 int tempPibot=0;

 while(count>0)//순정렬일 경우를 위해 0보다 작을경우도
 {
  j=0;
  for(i=l; i<=r; i++)
  {
   if(a[i+1] == 0)
    tempArray[j]=i;
   else if(a[i]>a[i+1])
   {
    tempArray[j]=i;
    j++;
    tempNum++;
   }
  }

  wall=0;

  if (flag==0) //한번만실행후 무시
  {
   count=tempNum-1; // 루프 돌 횟수를 count에 저장
   flag=1;
  }

  for(k=0;k<tempNum/2;k++)
  {
   m = 2*k; //묶음 갯수가 홀수 일 경우 마지막은 연산하지 않도록
   if(tempArray[m]==0)
    break;
   tempPibot = wall;
   p1 = tempArray[m];
   p2 = tempArray[m+1];

   wall = p2;
   cnt1 = p1-tempPibot; //앞 묶음 -- 문제 두번째 병합부터 카운트 오류. flag를 줄까?
   cnt2 = p2-p1; //뒷 묶음

   position = p2; //배열에 넣을 위치

   while(cnt1 != 0 || cnt2 != 0)//두묶음 모두 끝나면 나감
   { 
    if (cnt1 == 0) //한쪽묶음이 끝나면 다른 한쪽만 집어넣음
    {
     b[position] = a[p2];
     p2--;
     position--;
     cnt2--;
    }
    else if (cnt2 == 0)
    {
     b[position] = a[p1];
     p1--;
     position--;
     cnt1--;
    }
    else if(a[p1]<a[p2]) //큰값을 찾아 배열 뒤에서 부터 넣음
    {
     b[position] = a[p2];
     p2--;
     position--;
     cnt2--;
    }
    else if(a[p1]>=a[p2])
    {
     b[position] = a[p1];
     p1--;
     position--;
     cnt1--;
    }
   }
  }

  for(i=l; i<=wall; i++) // 합병한 것들만 다시 옮김 --> 마지막 묶음이 하나 남았을 경우때문에 wall 사용
   a[i] = b[i];

  tempNum=0; // 묶음갯수 초기화
  count--;

 }
}

void main(void)
{
 int i, a[N+1] = {-1,1,2,3,4,5};
 int j,k,l=N;
 int t=N;
 //double start_time;

 //srand(time(NULL));
 //for (i = 1; i <= N; i++) a[i] = rand();
 //printList(a);
 //start_time = clock();

 //for ( i = 1; i<=N; i++)
 //{
 // a[i]=t;
 // t--;
 //}//역순배열원소

 //for ( i =1; i<=N ; i++) a[i]=i; //정렬된 원소
 //printList(a);

 NaturalMergeSort(a, 1, N);

 //printList(a);

 //cout << "자연합병(랜덤) 정렬의 실행 시간 (N = " << N << ") : " <<
  clock() - start_time << endl;
 //CheckTime(a, N);
}

 

 

 

 

2. 개선

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

using namespace std;

const int N= 10000000;
int a[N+1];
int b[N+1];
const int TRUE = 1;
const int FALSE = 0;
int run[N+1];

inline void swap(int a[], int i, int j)
{
 int t = a[i]; a[i] = a[j]; a[j] = t;
}

void CheckTime(int a[], int n)
{
  int i, Sorted;
  Sorted = TRUE;
  for (i = 1; i < n; i++) {
    if (a[i] > a[i+1]) Sorted = FALSE;
    if (!Sorted) break;
  }
  if (Sorted) cout << "정렬 완료." << endl;
  else cout << "정렬 오류 발생." << endl;
}

void printList(int a[], int n)
{
 int i;
 for (i = 1; i < n; i++)
  cout << a[i] << ", ";
 cout << a[i] << endl;
}

void merge(int a[], int l, int m, int r)
{
 int i, j, k;
 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--];
}

int makeRun(int a[], int run[])
{
 int i = 1, j = 1;
 for (i = 1; i <= N; i++) {
  if (a[i] > a[i+1]) {
   run[j++] = i;
  }
 }
 //printList(run, j-1);
 return j-1;
}

int moveRun(int run[], int cnt)
{
 int i, j = 1;
 for (i = 2; i <= cnt; i += 2) run[j++] = run[i];
 if ((cnt % 2) != 0) run[j] = run[i-1]; // cnt가 홀수일 때 마지막 run 처리
 else j--;
 //printList(run, j);
 return j;
}

void NaturalMergeSort(int a[], int n)
{
 int i, num;
 int cnt; // number of runs
 //int run[N+1];
 run[0] = 0;
 cnt = makeRun(a, run);
 while (cnt > 1) {
  if ((cnt % 2) != 0) num = cnt-1; // cnt가 홀수일 때는 cnt 값을 하나 감소
  else num =  cnt;
  for (i = 1; i <= num; i += 2)
   merge(a, run[i-1]+1, run[i], run[i+1]);  
  
  //printList(a, N);
  cnt = moveRun(run, cnt);
 }
}

void main()
{
 //int i;
 //double start_time;

 //srand(time(NULL));
 //for (i = 1; i <= N; i++) a[i] = rand();

 //start_time = clock();

 NaturalMergeSort(a, N);
 //cout << "자연합병 정렬의 실행 시간 (N = " << N << ") : " <<
  clock() - start_time << endl;
 //CheckTime(a, N);
}