Методы сортировки и их примеры

 

Разделение следует применять  для подмассивов,   длина которых  больше 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);//перерисовка содержимого  окна