,,,
Ҡ
- Visual C ++
: " . "
1
2 ߠ VISUALC++
2.1
2.2 Sort
3
- , - , .
- , , , , .
- , .
Sort , , .
Sort .
: SORT, Visual C++, , , , .
. . , , , , . ( ).
- Visual C++, , Windows. Microsoft Visual C++, Microsoft Developer Studio 6.0.
Microsoft Developer Studio 6.0 , , ; , , .
, , , , , .
1
"Sort", . : (quicksort), (). .
2 VISUAL C++
Visual C++ - , . , IDE (Integrated Development Environment). IDE , . , . , , IDE.
Visual C++ . () . , , , , Image Editor ( ). Visual C++ ( ) , , .
, Visual C++ - , .. ( ). .
, Visual C++ , , . Visual C++ .
Microsoft Visual C++ 6.0. Visual C++ 6.0, , . , , , Visual C++ , .
Visual C++ 6.0 Windows 95 Windows 2000. , , Pentium, - 32 ( 200 ).
2.1
, , () ( ). . (., ). , . , . , . :
- ,
- ,
S - .
, n - ( - ). :
- , ;
- , .
, ,
"", , .
, .
(, , )
n**2 .
n*log2(n) : ,
, " ".
,
.
(
).
"".
(n-1)
. 1 2
, , ,
R1 R2 . R2 R3,
R3 R4 .. , "",
.
n - .
n-1, n-2, ... , 2
, .
,
. ,
, .
, .
.
""
n(n-1)/2 n(n-1)/2 (
, ).
n**2 .
.
. -
.
. , , , : (, "" "dcab") , , (, "d"), . . . . , , - . , .
.
, , . , . , . , , .
, , . , . , , .
-. , . , 9, 5, 3, 2, 1, . , , , . /, - . , , . , .. . . , , , . . n**1.2. , . , , , .
. n. , , , ( ). , , . , . , . , h (h ). h1, .
h1=[n/2], hi=h((i-1)/2).
, h1 :
h1=2**k+1 , 2**k < n <= 2**(k+1).
h1 ,
i, i+h1, i+2*h1, ..., i+mi*h1.
i=1,2,...,h1; m[i] - , i+m[i]*hi <= n.
h2<h1 , i, i+h2, ..., i+m[i]*h2. , h[l] (h1>h2>...>hl). . , , n /4, . n*(log2(n))**2 .
(Quicksort).
. . , , , , - . . , . i j . K[i] K[j], , j 1, . , K[i]>=K[j], R[i] R[j] . i, 1, j , . j 1, i , .. , i<j.
, , , . , . , - . , ( , ). , .. , , . , , . , .
, 9, .
. , 20 , 10**7 . , , . n*log(n) n - , m - , .
, . n, .. .
2.2 Sort
AppWizard , Windows- , , . : Project - MFC AppWizard (exe). AppWizard:
Step 1: Single document
Step 2:
Step 3:
Step 4: 3D controls, Docking ToolBar
Step 5: As a statically linked library
Step 6:
AppWizard MFC, .. . , :
CSortApp. CSortApp . CSortApp theApp. CWinApp theApp.
CSortView. CSortView . - Create CFrameWnd, Windows , C++-. ShowWindow UpdateWindow, - , .
WinMain, , CWinApp. , Sort, , . , , , . Microsoft Visual C++ 6.0, Microsoft Foundation Class (MFC) Library 6.0, , , .
MFC 140 , Windows-. , , , .. Sort 40 , Windows. :
Format ;
InvalidateRect Invalidate WM_PAINT;
DestroyWindow ;
PostQuitMessage WM_DESTROY;
ShowWindow ;
UpdateWindow ;
TextOut ;
UpdateWindow, . . Windows (message queue) , Windows. , Windows , . , message . Windows , WM (window message) . :
WM_CREATE , Windows View. , Create, .. , . , OnCreate Windows-, . OnInitialUpdate.
- OnDraw(). - CView; , , . , , . OnDraw, - , Windows, - Invalidate ( InvalidateRect) . Invalidate OnDraw.
Windows , (device context), . MFC ++- CDC, OnDraw ( ) . , - CDC, .
OnDraw , .
, Windows WM_COMMAND, . , :
ID_QUIK (quicksort) . .
ID_SHELL . .
ID_PUZIROK (). .
兔, ID_APP_ABOUT, , .
ID_APP_EXIT . OnDestroy, .
3
Sort.exe, . , . , . , , , , . .
, (quicksort), (). . . .
. , : , .
, . , .
: Pentium 133, 16 MB RAM, Windows 95/98/2000 NT/XP.
Visual C++. .
, , , "- ". , , - .
- .
Visual C++.
#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::Dump(CDumpContext& dc) const
{
CView::Dump(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::part(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);
}
1. . Windows 95. : BHV - , 1997, silt.
2. ., . Windows 98. . , 1999.-864 .: .- . . . ..
3. . ++ 21 . - , 2000.-816 .: . - .. .
4. . . ++. , 1997.- 696 .: .
5. . Visual C++. , 1999.-864 .: .. - .. ., . .
7. .
Ҡ
Copyright (c) 2024 Stud-Baza.ru , , , .