Program To Sort Given Numbers Using Mergesort

// progrem to find oredring of matrix chain multiplication


#include<iostream.h>
#include<conio.h>

#define MAX 15

#define INF 4294967295

class matrixchain
{
	private:
		int num,p[MAX+1],n;
		void print(int [][MAX],int,int);
		void matrix_chain_order();

	public:
		void setdata();
		void print_order();
};

void matrixchain::print(int s[MAX][MAX],int i,int j)
{
	if(i==j)
		cout<<" A"<<num++<<" ";
	else
	{
		cout<<" ( ";
		print(s,i,s[i][j]);
		cout<<" x ";
		print(s,s[i][j]+1,j);
		cout<<" ) ";
	}
}

void matrixchain::matrix_chain_order()
{
	unsigned int q;
	unsigned long m[MAX][MAX]={0};
	int s[MAX][MAX]={0};
	int l,j,i,k;

	for(l=2;l<=n;l++)
		for(i=1;i<=n-l+1;i++)
		{
			j=i+l-1;
			m[i][j]=INF;
			for(k=i;k<j;k++)
			{
				q=m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
				if(q < m[i][j])
				{
					m[i][j]=q;
					s[i][j]=k;
				}
			}
		}

	cout<<"\n\nNumber of Multiplications are: "<<m[1][n];

	num=1;

	cout<<"\n\nOrder of Multiplication is: \n\n\t\t";
	print(s,1,n);

}

void matrixchain::setdata()
{
	int i;

	cout<<"\nEnter number of matrices: ";
	cin>>n;

	for(i=1;i<=n;i++)
	{
		cout<<"\nEnter "<<i<<" matrix size: ";
		cin>>p[i-1]>>p[i];
	}
}

void matrixchain::print_order()
{
	int i,j;

	matrix_chain_order();

}

void main()
{
	 matrixchain mc;
	 clrscr();

	 mc.setdata();

	 mc.print_order();

	 getch();
}