합병정렬(MERGE SORT)

// win4.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include<iostream>
#include<iomanip>
using namespace std;

class CWATmergesort
{ 
private: 
 int *x,*y,*z; 
 int items1,items2; 
public: 
 CWATmergesort(int,int); 
 ~CWATmergesort(); 
 void input1(int []); 
 void input2(int []); 
 void msort(int [], int); 
 void display(); 
 void sort();
};


CWATmergesort::CWATmergesort(int p,int q)
{ 
 items1=p; 
 items2=q; 
 x=new int[items1]; 
 y=new int[items2]; 
 z=new int[items1+items2];
}

CWATmergesort::~CWATmergesort()
{ 
 delete [] x; 
 delete [] y; 
 delete [] z;
}

void CWATmergesort::input1(int a[])
{ 
 for(int i=0;i<items1;i++) 
  x[i]=a[i]; 
 msort(x,items1); 
 cout<<"\n Sorted first array :"; 
 for(i=0;i<items1;i++) 
  cout<<setw(5)<<x[i];
}

void CWATmergesort::input2(int b[])
{ 
 for(int i=0;i<items2;i++) 
  y[i]=b[i]; 
 msort(y,items2); 
 cout<<"\n Sorted second array : "; 
 for(i=0;i<items2;i++) 
  cout<<setw(5)<<y[i];
}

void CWATmergesort::msort(int m[],int n)
{
int swap=1; 
 for(int i=0;i<n && swap==1;i++) 
 { 
 swap=0; 
 for(int j=0;j<n-(i+1);j++) 
  { 
  if(m[j]>m[j+1]) 
   { 
   int temp; 
   temp=m[j]; 
   m[j]=m[j+1]; 
   m[j+1]=temp; 
   swap=1; 
   } 
  } 
 }
}

 void CWATmergesort::display()
{ 
 cout<<"\n Sorted elements are :"; 
 for(int i=0;i<items1+items2;i++) 
  cout<<setw(5)<<z[i];
}

void CWATmergesort::sort()
{ 
 int i,j,k; 
 i=j=k=0; 
 while((i<items1) && (j<items2)) 
 {
if(x[i]<y[j]) 
  {
 z[k]=x[i]; 
  i++; 
  k++; 
  } 
 else 
  { 
  if(x[i]>y[j]) 
   { 
   z[k]=y[j]; 
   j++; 
   k++; 
   } 
  else 
   { 
   z[k]=x[i]; 
   i++; 
   j++; 
   k++; 
   } 
  } 
 } 
 while(i<items1) 
 { 
 z[k]=x[i]; 
 i++; 
 k++; 
 } 
 while(j<items2) 
 { 
 z[k]=y[j]; 
 j++; 
 k++; 
 }
}

int main()
{ 
 int elements1[100]={1,2,13,4,7};   
 int n1=5;
 int elements2[100]={111,222,33,44,77};   
 int n2=5;

  CWATmergesort obj(n1,n2); 
 obj.input1(elements1); 
 obj.input2(elements2); 
 obj.sort(); 
 obj.display(); 
 return 0;
}

<결과>
 Sorted first array :    1    2    4    7   13
 Sorted second array :    33   44   77  111  222
 Sorted elements are :    1    2    4    7   13   33   44   77  111  222
Press any key to continue