. , , ,

,,,

. — ,

Ҡ

 

- Visual C ++

: " . "

: :

. . -03-1

.. ..

2004


1

2 ߠ VISUALC++

2.1

2.2 Sort

3


 

: 24 .

- , - , .

- , , , , .

- , .

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. .

Ҡ

 

 

 

! , , , .
. , :