// 排序算法比較Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "排序算法比較.h"
#include "排序算法比較Dlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg dialog

CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CMyDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CMyDlg)
	m_num = 0;
	m_info = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	select=0;
	count=0;
}

void CMyDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMyDlg)
	DDX_Text(pDX, IDC_EDIT_N, m_num);
	DDV_MinMaxInt(pDX, m_num, 500, 5000);
	DDX_Text(pDX, IDC_EDIT_OUTPUT, m_info);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMyDlg, CDialog)
	//{{AFX_MSG_MAP(CMyDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_RADIO1, OnRadio1)
	ON_BN_CLICKED(IDC_RADIO2, OnRadio2)
	ON_BN_CLICKED(IDC_RADIO3, OnRadio3)
	ON_BN_CLICKED(IDC_RADIO4, OnRadio4)
	ON_BN_CLICKED(IDC_RADIO5, OnRadio5)
	ON_BN_CLICKED(IDBEGIN, OnBegin)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg message handlers

BOOL CMyDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CMyDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CMyDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CMyDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CMyDlg::OnRadio1() 
{
	// TODO: Add your control notification handler code here
	select=1;
	
}

void CMyDlg::OnRadio2() 
{
	// TODO: Add your control notification handler code here
	select=2;
}

void CMyDlg::OnRadio3() 
{
	// TODO: Add your control notification handler code here
	select=3;
}

void CMyDlg::OnRadio4() 
{
	// TODO: Add your control notification handler code here
	select=4;
}

void CMyDlg::OnRadio5() 
{
	// TODO: Add your control notification handler code here
	select=5;
}

void CMyDlg::OnBegin() 
{
	// TODO: Add your control notification handler code here
	UpdateData(TRUE);
		CString str=m_info;
		CString szText;
		low=1;
		high=m_num-1;
	for(int i=1; i<=m_num-1; ++i) 
		a[i]=rand();


	switch(select)
		{
			case 1:
				SelectSort();
				break;
			case 2:
				InsertionSort();
				break;
			case 3:
				BottomUpSort();
				break;
			case 4:
				MergeSort(low,high);
				break;
			case 5:
				QuickSort(low,high);
				break;
			default:
				exit(0);
		}




		szText.Format("%d",count);
			str+="\n執(zhí)行了"+szText+"次比較！";
			GetDlgItem(IDC_EDIT_OUTPUT)->SetWindowText(str);

}

void CMyDlg::SelectSort()
{
	int pos;											//目前最小的數(shù)字的位置     
   int i,j,temp;									//temp存最小數(shù)字

   for(i=1; i<m_num; ++i)
   {
      pos=i;
      temp=a[i];
      for(j=i+1; j<m_num; j++){						//查找最小的字符
		  if(a[j]<temp)
          {
            pos=j;									//新的最小字符的位置
            temp=a[j];
		  }
		  count++;
	  }
      a[pos]=a[i];									//交換位置
      a[i]=temp;
   }
}

void CMyDlg::InsertionSort()
{
	int i, j;

		for(i=2; i<m_num; i++)
		{
			if(a[i]<a[i-1])
			{
				a[0]=a[i];						//a[0]作為哨兵
				a[i]=a[i-1];
				j=i-1;
				while(a[--j]>a[0])
				{
					a[j+1]=a[j];
					count++;
				}
				a[j+1]=a[0];
			}
		}
}

void CMyDlg::MERGE(int l,int m,int h)
{
	int s1=l, s2=m+1;
	int length=h-l+1;
	int t[5000];
	for(int i=0; s1<=m && s2<=h; i++){
		count++;
		if(a[s1]>a[s2]) 
			t[i]=a[s2++];
		else 
			t[i]=a[s1++];
	}
	while(s1<=m) 
		t[i++]=a[s1++];
	while(s2<=h) 
		t[i++]=a[s2++];
	i=0;
	while(l<=h) 
		a[l++]=t[i++];
}
/*MERGEMERGEMERGEMERGEMERGEMERGEMERGEMERGEMERGE*/

/********************************************/
/*              BottomUpSort                */
/********************************************/
void CMyDlg::BottomUpSort()
{
	int t=1;
	int s,i;
	while(t<m_num-1){
		s=t; 
		t=2*s; 
		i=1;
		while(i+t<=m_num-1){
			MERGE(i, i+s-1, i+t-1);
			i=i+t;
		}
		if(i+s<m_num) MERGE(i, i+s-1, m_num-1);
	}
}


/********************************************/
/*                MergeSort                 */
/********************************************/

void CMyDlg::MergeSort(int low,int high)
{
	int mid;
	if(low<high){
		mid=(low+high)/2;
		MergeSort(low,mid);
		MergeSort(mid+1,high);
		MERGE(low,mid,high);
	}
}



/********************************************/
/*                QuickSort                 */
/********************************************/
int CMyDlg::Parttion(int low,int high)				//快速排序的一趟
{
	a[0]=a[low];									//作為樞軸
	while(low<high)
	{
		count++;
		while( low<high && a[high]>=a[0] )
		{
			count++;
			--high;
		}
		count++;
		a[low]=a[high];								//將比樞軸小的記錄移到低端
		while( low<high && a[low]<=a[0] )
		{
			count++;
			++low;
		}
		count++;
		a[high]=a[low];								//將比樞軸大的記錄移到高端
	}
	count++;
	a[low]=a[0];
	return low;
}

void CMyDlg::QuickSort(int low,int high)
{
	int pivotloc;									//pivotloc為樞軸
	if(low<high){
		count++;
		pivotloc=Parttion(low,high);				//將a[]一分為二
		QuickSort(low,pivotloc-1);				//對低子表遞歸排序
		QuickSort(pivotloc+1,high);				//對高子表遞歸排序
	}
 
}

void CMyDlg::OnButton1() 
{
	// TODO: Add your control notification handler code here
	CAboutDlg aboutdlg;
	aboutdlg.DoModal();
	
}