분할정복법

Study/C++

분할정복법

코딩하는 야구쟁이 2011. 9. 29. 20:51

#include <iostream>

using namespace std;

int s[301];
int t[301];
int num1;

static int c=0;

//###################################################
// 계속 숫자 2개만을 비교하기때문에 인자값은 2개만..
// 두개를 비교하여 작은수는 버리고, 큰수를 남겨 둔다.
//###################################################
void is_solution(int left,int right)
{	
	cout<<"왼쪽의"<<t[left]<<"와 오른쪽의 "<<t[right]<<"을 비교합니다."<<endl;
	
	if(t[left] < t[right]) t[left] = t[right];
	else t[right] = t[left];
}

void merge_sort(int left, int right)
{
	if(left<right)
	{
		int mid=(left+right)/2;
		merge_sort(left, mid);
		merge_sort(mid+1, right);
		is_solution(left,right);
	}
	else
	{
		t[c] = s[left];
		c++;
	}
}

void main()
{
	int i;
	// 몇개의 숫자를 입력할껀지 입력
	cout<<"몇개의 숫자를 입력할껀가요?"<<endl;
	cin>>num1;
	
	// num1만큼 숫자를 입력
	cout<<"숫자를 입력해주세요"<<endl;
	for(i=0;i<num1;i++)
	{
		cin>>s[i];
	}
	
	merge_sort(0,num1-1);
	
	cout<<endl;
	cout<<endl;
	
	// 입력한 원본을 그대로 살려두었음을 보여주기 위해 print
	cout<<"입력한 값들입니다"<<endl;
	for(i=0;i<num1;i++)
	{
		cout<<s[i];
	}
	cout<<endl;
	
	// 비교배열의 상황(필요는 없지만 print)
	cout<<"비교시킨 배열들의 현황입니다."<<endl;
	for(i=0;i<num1;i++)
	{
		cout<<t[i];
	}
	cout<<endl;
	
	// 가장큰수는 배열의 가장 왼쪽 과 가장 오른쪽에 남아 있게 됩니다.
	cout<<endl;
	cout<<t[0]<<endl;
}