#include "stdafx.h"
#include "Sort.h"
#include "SortDoc.h"
#include "SortView.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
//объявление глобальных переменных
int mas[20]={30,5,17,8,1,14,12,3,77,2,45,89,33,21,6}, mas2[20], kol=15, count=0;
CString str;
bool sort=false;
int metod=0;
//1- quicksort
//2- shell
//3- пузырька
/////////////////////////////////////////////////////////////////////////////
// CSortView
IMPLEMENT_DYNCREATE(CSortView, CView)
BEGIN_MESSAGE_MAP(CSortView, CView)
//{{AFX_MSG_MAP(CSortView)
ON_COMMAND(ID_QUICK, OnQuick)
ON_COMMAND(ID_PUZIROK, OnPuzirok)
ON_COMMAND(ID_SHELL, OnShell)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CSortView construction/destruction
CSortView::CSortView()
{
// TODO: add construction code here
}
CSortView::~CSortView()
{
}
BOOL CSortView::PreCreateWindow(CREATESTRUCT& cs)
{
// TODO: Modify the Window class or styles here by modifying
// the CREATESTRUCT cs
return CView::PreCreateWindow(cs);
}
/////////////////////////////////////////////////////////////////////////////
// CSortView drawing
//функция вывода данных на экран
void CSortView::OnDraw(CDC* pDC)
{
CSortDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
int i;
//выводим исходный массив на экран
for(i=0;i<kol;i++)
{
str.Format("%d,",mas[i]);//формирование строки
pDC->TextOut(10+i*20,10,str);//вывод на экран
}
//если был выбран какой-нибудь метод сортировки
if(sort)
{
if(metod==1)//если выбран Quicksort
pDC->TextOut(10,40,"Обменная сортировка с разделением (quicksort)");//вывод строки на экран
if(metod==2)//если выбран Shell
pDC->TextOut(10,40,"Метод Шелла");//вывод строки на экран
if(metod==3)//если выбран Bubble
pDC->TextOut(10,40,"Метод прямого обмена (Пузырька)");//вывод строки на экран
//выводим отсортированный массив
for(i=0;i<kol;i++)
{
str.Format("%d,",mas2[i]);//формирование строки
pDC->TextOut(10+i*20,80,str);//вывод строки на экран
}
str.Format("Количество перестановок в нашем случае: %d",count);//формирование строки
pDC->TextOut(10,110,str);//вывод строки на экран
if(metod==3)//если был выбран метод "Пузырька"
{
str.Format("Максимальное количество перестановок для массива из %d элементов методом 'Пузырька': %d",kol, kol*(kol-1)/2);//формирование строки
pDC->TextOut(10,140,str);//вывод строки на экран
}
}
}
/////////////////////////////////////////////////////////////////////////////
// CSortView diagnostics
#ifdef _DEBUG
void CSortView::AssertValid() const
{
CView::AssertValid();
}
void CSortView:
ump(CDumpContext& dc) const
{
CView:
ump(dc);
}
CSortDoc* CSortView::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSortDoc)));
return (CSortDoc*)m_pDocument;
}
#endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CSortView message handlers
//при выборе сортировки Quicksort
void CSortView::OnQuick()
{
//объявление локальных переменных
sort=true;
metod=1;
int i;
count=0;
for(i=0;i<kol;i++)
{
mas2[i]=mas[i];
}
quicksort(0, kol-1);//вызов функции quicksort
Invalidate(true);//перерисовка содержимого окна
}
//при выборе сортировки Shell
void CSortView::OnShell()
{
//объявление локальных переменных
sort=true;
metod=2;
int ii,t=5,i,j, k, s, m, h[6], x;
count=0;
for(ii=0;ii<kol;ii++)
{
mas2[ii]=mas[ii];
}
h[1]=9; h[2]=5; h[3]=3; h[4]=2; h[5]=1;
////////////////////////////////////////////
АЛГОРИТМ
for(m=1;m<=t;m++)
{
k=h[m];
s=-k;
for(i=k+1; i<=kol;i++)
{
x=mas2[i];
j=i-k;
while (x<mas2[j] && j<kol)
{
mas2[j+k]=mas2[j];
j=j-k;
}
mas2[j+k]=x;
count++;
}
}
x=mas2[0];
mas2[0]=mas2[1];
mas2[1]=x;
////////////////////////////////////////////
Invalidate(true);//перерисовка содержимого окна
}
//при выборе сортировки Bubble
void CSortView::OnPuzirok()
{
//объявление локальных переменных
int dop;
bool end;
count=0;
sort=true;
metod=3;
int i, j;
for(i=0;i<kol;i++)
{
mas2[i]=mas[i];
}
////////////////////////////////////////////
//АЛГОРИТМ
for(i=0;i<kol;i++)
{
end=true;
for(j=i+1;j<kol;j++)
{
if(mas2[i]>mas2[j])
{
dop=mas2[i];
mas2[i]=mas2[j];
mas2[j]=dop;
end=false;
count++;
}
}
if(end==true) break;
}
/////////////////////////////////////////////
Invalidate(true);//перерисовка содержимого окна
}
//функция быстрого поиска
void CSortView::quicksort(int l, int r)
{
int i, j;
i=l;j=r;
{
part(l, r, i, j);
if(i<r)quicksort(i, r);// переход к сортировке левой части
if(j>l)quicksort(l, j);// переход к сортировке правой части
}
}
//функция поиска по частям
void CSortView:
art(int l, int r, int &i, int &j)
{
int x, dop;
i=l;
j=r;
x=(l+r)/2;
do
{
while(mas2[i]<mas2[x])
i++;
while(mas2[j]>mas2[x])
j--;
if(i<=j)
{
dop=mas2[i];
mas2[i]=mas2[j];
mas2[j]=dop;
i++;j--;count++;
}
}
while(i<j);
}