Визуализация алгоритмов сортировки

СОРТИРОВКА, АЛГОРИТМ СОРТИРОВКИ, СОРТИРОВКА РАСЧЕСКОЙ, СОРТИРОВКА ПЕРЕМЕШИВАНИЕМ, С++
Объект исследования курсовой работы являются алгоритмы сортировки.
Цели выполнения курсовой работы: программная реализация алгоритмов сортировки перемешиванием (Shaker sort) и расческой (Comb sort).
Метод исследования – алгоритмы сортировки перемешиванием (Shaker sort) и расческой (Comb sort).
Стягивающее дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь рёбрам.
Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение "<" для чисел. Алгоритм сортировки – это алгоритм для упорядочивания элементов в списке.
Различит два вида сортировок: внутренняя и внешняя. В работе будут рассмотрены две внутренних сортировки перемешиванием (Shaker sort) и расческой (Comb sort). Оба рассматриваемых алгоритма являются улучшением алгоритма сортировка пузырьком (bubble sort).
Для проведения исследования разработано приложение на языке C++. Приложение имеет графический пользовательский интерфейс. Визуализация алгоритма позволяет просмотреть процесс сортировки массива по шагам.
Программа может быть использована как вспомогательное учебное пособие при изучении алгоритмов сортировок.
Программа написана на языке С++ с использованием среды разработки Visual Studio 2019.
СОДЕРЖАНИЕ
TOC \o "1-1" \t "Заголовок 4;2" 2.1Введение3
2.2Анализ задания и выбор метода решения.4
2.2.1 Анализ задания.4
2.2.2 Выбор метода решения.4
2.2.3 Аналитическое описание метода5
2.3Реализация метода решения задачи.8
2.3.1 Обоснование метода контроля входной информации.8
2.3.2Обоснование метода построения программы.8
2.3.3Выбор структур входных, рабочих и выходных данных.10
2.3.4Проектирование программы.10
2.3.5Анализ и верификация результатов.11
2.4Заключение.12

2.5 Приложение А. Описание программы.
Текст программы. ТПЖА. 18226-01 13 01 ЛУ13
2.6 Приложение Б. Текст программы.
Текст программы. ТПЖА. 18226-01 34 01-1 ЛУ19
2.7 Приложение В. Руководство оператора.
Описание программы. ТПЖА. 18226-01 12 01-1 ЛУ40
2.8. Приложение Г. Библиографический список 47
. ВВЕДЕНИЕ
Алгоритм сортировки - это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин.
Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти. Время - основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Память - ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных.
Целью курсовой работы является реализовать алгоритмы сортировки перемешиванием (Shaker sort) и расческой (Comb sort).
Для достижения поставленной цели необходимо:
-провести анализ задания;
-выбрать метод решения задачи;
-дать аналитическое описание метода;
-выбрать и обосновать методы контроля входной информации;
-выбрать и обосновать методы построения программы;
-описать входные, выходные и рабочие данные;
-провести верификацию полученных результатов;
-составить документацию в соответствии с ЕСПД: «Описание программы», «Текст программы» и «Руководство оператора».
Анализ задания и выбор метода решения
Анализ задания
В рамках курсовой работы необходимо реализовать программу для визуализации алгоритмов сортировки.
Необходимо реализовать алгоритмы сортировки перемешиванием (Shaker sort) и расческой (Comb sort)
Программу необходимо разработать на языке С++ в среде разработки Visual Studio 2019. Программа должна иметь удобный пользовательский интерфейс для ввода исходных данных и вывода результата.
Для визуализации необходимо предусмотреть пошаговое выполнение алгоритма с графической иллюстрацией каждого шага.
Выбор метода решения
Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение "<" для чисел. Алгоритм сортировки – это алгоритм для упорядочивания эле-ментов в списке.
Различит два вида сортировок: внутренняя и внешняя.
Внутренняя сортировка использует в оперативную память компьютера для размещения всех сортируемых данных. Это позволяет получить доступ к данным в любом порядке (т.е. используется модель памяти с произвольным доступом). Внешняя сортировка применяется тогда, когда объем упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память.
В работе будут рассмотрены две внутренних сортировки перемешиванием (Shaker sort) и расческой (Comb sort).
Оба рассматриваемых алгоритма являются улучшением алгоритма сортировка пузырьком (bubble sort). Это простой алгоритм сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Сортировка методом пузырька имеет сложность O(n^2). Для понимания и реализации это – простейший алгоритм сортировки, но эффективен он лишь для небольших массивов.
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки.
Далее рассмотрим два возможных улучшения алгоритма.
Аналитическое описание метода
Сортировка перемешиванием (Коктейльная сортировка, шейкерная сортировка, шейкер-сортировка) (Cocktail sort) – разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие - к началу.
Если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
При движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Образно алгоритм можно описать так: на каждом шаге основного цикла рассматривается массив A[L]÷A[R], после выполнения двух внутренних циклов минимальный и максимальный элемент в исходном массиве перетекают к краям, минимальный в – a[L], максимальный – в A[R]. Пусть максимальный элемент имеет индекс k, тогда массив можно изобразить так: a[L],a[1],..,a[k-1],A[k],a[k+1],..,a[R];После сравнения A[k] с a[k+1] значение A[k] перейдет в k+1-ую ячейку, после сравнения k+1-ой c k+2-ой – в k+2-eю, и так далее, пока он не сместится в крайне правое положение с индексом Right. Аналогично для минимального. После выполнения цикла по всем подмассивам он отсортируется.
Алгоритм.
1. Выполняем сортировку пузырьком из конца в начало
2. Выполняем сортировку пузырьком в обратном направлении
3. Повторяем пункты 1 и 2 пока промежуток не окажется равным 0.
Сортировка расчёской (Comb sort) - это упрощённый алгоритм сортировки, улучшающий сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея – устранить маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (большие значения в начале списка, не представляют проблемы для сортировки пузырьком).
В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица (сортировка Шелла также основана на этой же идее).
Иными словами – это усовершенствованная пузырьковая сортировка с предварительными «грубыми» проходами.
Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди. Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины, называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива, разделённого на фактор уменьшения (результат округляется до ближайшего целого). Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.
Алгоритм.
1. Для шага определяем величину промежутка d
2. Выполняем сортировку пузырьком с шагом d
3. Повторяем пункты 1 и 2 пока промежуток не окажется равным 0.

Реализация метода решения задачи
Обоснование метода контроля входной информации
Работа состоит из нескольких частей:
-изучение теоретического материала источников [1]-[6];
-разработка пользовательского интерфейса программы;
- реализация алгоритма решения задачи.
Работа с программой для пользователя будет состоять из следующих шагов:
- ввести целочисленный массив данных;
- выбрать алгоритм сортировки;
-выполнить сортировку (при необходимости выполнить пошаговый просмотр алгоритма).
Исходные данные необходимо проверить на корректность. Массив должен состоять из целых чисел. Введенная пользователем строка разбивается на отдельные лексемы разделенные знаком пробелом и проверяется возможность преобразования к целому числу каждой лексемы. В случае обнаружения ошибок программа должна выдать сообщение.
Обоснование метода построения программы
Интерфейс программы показан на рисунке 2.1.

Рисунок 2.1 – Интерфейс программы
На форме приложения расположены следующие элементы управления:
-pictureBoxPrevious (PictureBox) – область для вывода состояния массива на предыдущем шаге;
-pictureBoxCurrent (PictureBox) – область для вывода состояния массива н текущем шаге;
- textBoxData (TextBox) – текстовое поле для ввода элементов массива;
- buttonStart (Button) – кнопка для выполнения алгоритма сортировки;
-buttonToStart (Button) – кнопка «|<» (вернуться к первому шагу алгоритма);
-buttonPrevious (Button) – кнопка «<» (вернуться на один шаг алгоритма);
-buttonNext (Button) – кнопка «>» (выполнить один шаг алгоритма вперед);
-buttonToFinish (Button) – кнопка «>||» (перейти к последнему шагу алгоритма);
-buttonStopAnimation (Button) – кнопка «Stop» (остановить визуализацию);
-buttonStartAnimation (Button) – кнопка «Play» (запустить визуализацию);
-numericUpDown (NumericUpDown) – поле ввода с инкрементом/декрементом для выбора шага сортировки для отображения;
-comboBox (ComboBox) – список для выбора алгоритма сортировки;
- timer1 (Timer) – таймер для реализации визуализации алгоритма;
-numericUpDownInterval (NumericUpDown) – поле ввода с инкрементом/декрементом для установки скорости сортировки;
-menuStrip1 (MenuStrip) –меню программы;
-label1, label2, label3, label4, label5, label6 (Label) – поясняющие надписи к элементам управления;
-labelComment (Label) - текстовая метка для вывода пояснения к текущему шагу алгоритма сортировки.
Выбор структур входных, рабочих и выходных данных
На вход программы подается массив целых чисел. Для ввода массива используется текстовое поле. При вводе необходимо осуществить контроль правильности ввода.
Результатом работы программы является этот же массив, но содержащий отсортированные данные.
Промежуточные результаты будут храниться в классе History. Данный класс содержит список элементов типа Element. Каждый элемент содержит информацию об одном шаге сортировки. Это необходимо для графического вывода результата. Элемент содержит:
a – содержимое массива;
mark - список помеченных элементов;
comment – комментарий к шагу алгоритма.
Проектирование программы
Программа визуализации сортировок состоит из следующих модулей:
-Form1.cpp –главный модуль программы, содержит функцию main, создает форму приложения;
-Form1.h - модуль содержит описание пользовательского интерфейса программы и обработчики событий;
-History.h – модуль содержит описание и реализацию классов для хранения пошагового выполнения сортировки.
Схема связи модулей программы показана на рисунке 2.5.
Form1.cpp
Form1.h
History.hForm1.cpp
Form1.h
History.h
Рисунок 2.5 – Схема связи модулей программы
Описание программы приведено в приложении А.
Анализ и верификация результатов
Рассмотрим пример выполнения программы.
Инструкция по пользованию программой приведена в приложении Б.
На рисунке 2.6 показан пример выполнения сортировки перемешиванием.

Рисунок 2.6 – Сортировка перемешиванием
На рисунке 2.7 показан пример выполнения сортировки расческой.

Рисунок 2.7 – Сортировка расческой
Из результатов видно, что оба алгоритма работают верно.

ЗАКЛЮЧЕНИЕ
В рамках курсовой работы разработана программа выполняющая визуализацию алгоритмов сортировки.
В процессе работы были изучены алгоритмы сортировки перемешиванием (Shaker sort) и расческой (Comb sort).
Для разработки использовался язык программирования С++ и среда разработки Visual Studio 2019. Приложение имеет графический пользовательский интерфейс. Визуализация алгоритма позволяет просмотреть процесс сортировки массива по шагам.
Приложение А
(обязательное)
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ
ФГБОУ ВО «ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет автоматики и вычислительной техники
Кафедра радиоэлектронных средств
УТВЕРЖДАЮ
Заведующий кафедрой РЭС
____________ А.П. Метелев
Визуализация алгоритмов сортировки
Описание программыЛист утверждения
Листов 2
ТПЖА.18226-01 13 01-ЛУ
Разработал студент группыИКТб-1301-04-24 ________________ (подпись) / А.Н. Черепанов /
Руководитель старший преподаватель кафедры РЭС ________________ (подпись) / Т.В. Наумович /
Киров 2020
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ
ФГБОУ ВО «ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет автоматики и вычислительной техники
Кафедра радиоэлектронных средств
Утвержден:
ТПЖА. 18226-01 13 01-ЛУ
Визуализация алгоритмов сортировки
Описание программы
Листов 6
ТПЖА.18226-01 13 01 ЛУ
Киров 2020
Аннотация
Документ содержит описание логической структуры программы, характеристики программы, способ загрузки, ее назначение, входные и выходные данные.
СОДЕРЖАНИЕ
TOC \t "Заголовок 3;1;Заголовок 5;2" 1.Общие сведения15
1.1.Обозначение и наименование15
1.2.ПО необходимое для функционирования15
1.3.Язык программирования15
2.Функциональное назначение15
3.Описание логической структуры15
3.1.Алгоритм программы15
4.Входные данные18
5.Выходные данные18

Общие сведения
Обозначение и наименование
Обозначение и наименование программы: «Сортировки».
ПО необходимое для функционирования
Для корректной работы программы на компьютере пользователя должны быть установлены:
-операционная система Windows 7 или версии выше;
-.NET Framework версии 4.0 или версии выше.
Язык программирования
Программа «Сортировки» написана на языке программирования C++. В качестве среды разработки использована среда Microsoft Visual Studio 2019.
Функциональное назначение
Программа предназначена для визуализации алгоритмов сортировки перемешиванием (Shaker sort) и расческой (Comb sort).
Описание логической структуры
Алгоритм программы
В основе программы лежат алгоритмы сортировок перемешиванием и расческой.
Блок-схема алгоритма сортировки перемешиванием показана на рисунке Б.1.
Рисунок Б.1 - Блок-схема алгоритма сортировки перемешиванием
Блок-схема алгоритма сортировки расческой показана на рисунке Б.2.
Рисунок Б.2 - Блок-схема алгоритма сортировки расческой
Оба алгоритма используют функцию обеспечивающую обмен двух элементов массива местами. Блок-схема функции показана на рисунке Б.3.

Рисунок Б.3 - Блок-схема алгоритма обмена элементов массива местами

Входные данные
Список входных данных для программы приведен в таблице В.1.
Таблица В.1 – Входные данные для программы
Имя Тип Назначение
comboBox->SelectedIndexIntАлгоритм выбранный пользователем
A Массив [in] Исходный массив
Выходные данные
Список выходных данных для программы приведен в таблице В.2. Таблица В.2 - Входные данные программы
Имя Тип Назначение
H HistoryПошаговая история сортировки
A Массив [in] Отсортированный массив
Приложение Б
(обязательное)
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ
ФГБОУ ВО «ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет автоматики и вычислительной техники
Кафедра радиоэлектронных средств
УТВЕРЖДАЮ
Заведующий кафедрой РЭС
____________ А.П. Метелев
Визуализация алгоритмов сортировки
Текст программы
Лист утверждения
Листов 2
ТПЖА.18226-01 34 01-1 ЛУ
Разработал студент группыИКТб-1301-04-24 ________________ (подпись) / А.Н. Черепанов /
Руководитель старший преподаватель кафедры РЭС ________________ (подпись) / Т.В. Наумович /
Киров 2020
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ
ФГБОУ ВО «ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет автоматики и вычислительной техники
Кафедра радиоэлектронных средств
Утвержден:
ТПЖА.18226-02 34 01-1 ЛУ
Визуализация алгоритмов сортировки
Текст программы
Листов 19
ТПЖА.18226-01 13 01-ЛУ
Киров 2020
Аннотация
Данный программный документ содержит полный текст программы на языке С++.
.
СОДЕРЖАНИЕ
TOC \u \t "Заголовок 8;1" 1 MyForm.h23
2 MyForm.cpp37
3 History.h38


1 MyForm.h#pragma once
#include "History.h"
namespace Sorts {
using namespace System;
using namespace System::ComponentModel;
using namespace System::Collections;
using namespace System::Windows::Forms;
using namespace System::Data;
using namespace System::Drawing;
/// <summary>
/// Summary for MyForm/// </summary>
public ref class MyForm : public System::Windows::Forms::Form
{
public:
MyForm(void)
{
InitializeComponent();
//
//TODO: Add the constructor code here
//
}
protected:
/// <summary>
/// Clean up any resources being used.
/// </summary>
~MyForm(){
if (components)
{
delete components;
}
}
private: System::Windows::Forms::PictureBox^ pictureBoxPrevious;
private: System::Windows::Forms::PictureBox^ pictureBoxCurrent;
protected:
protected:
protected:
private: System::Windows::Forms::Label^ label1;
private: System::Windows::Forms::Label^ label2;
private: System::Windows::Forms::TextBox^ textBoxData;
private: System::Windows::Forms::Label^ label3;
private: System::Windows::Forms::Button^ buttonStart;
private: System::Windows::Forms::Button^ buttonToStart;
private: System::Windows::Forms::Button^ buttonPrevious;
private: System::Windows::Forms::Button^ buttonStopAnimation;
private: System::Windows::Forms::Button^ buttonStartAnimation;
private: System::Windows::Forms::Button^ buttonNext;
private: System::Windows::Forms::Button^ buttonToFinish;
private: System::Windows::Forms::NumericUpDown^ numericUpDown;
private: System::Windows::Forms::Label^ label4;
private: System::Windows::Forms::ComboBox^ comboBox;
private: System::Windows::Forms::Label^ label5;
private: System::Windows::Forms::Timer^ timer;
private: System::Windows::Forms::NumericUpDown^ numericUpDownInterval;
private: System::Windows::Forms::Label^ label6;
private: System::Windows::Forms::Label^ labelComment;
private: System::Windows::Forms::MenuStrip^ menuStrip1;
private: System::Windows::Forms::ToolStripMenuItem^ fileToolStripMenuItem;
private: System::Windows::Forms::ToolStripMenuItem^ restrictionsToolStripMenuItem;
private: System::Windows::Forms::ToolStripSeparator^ toolStripMenuItem1;
private: System::Windows::Forms::ToolStripMenuItem^ exitToolStripMenuItem;
private: System::Windows::Forms::ToolStripMenuItem^ helpToolStripMenuItem;
private: System::Windows::Forms::ToolStripMenuItem^ aboutToolStripMenuItem;
private: System::Windows::Forms::ToolStripMenuItem^ directionToolStripMenuItem;
private: System::Windows::Forms::Label^ labelRestrict;
private: System::ComponentModel::IContainer^ components;
private:
/// <summary>
/// Required designer variable.
/// </summary>
#pragma region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
void InitializeComponent(void)
{
this->components = (gcnew System::ComponentModel::Container());
System::ComponentModel::ComponentResourceManager^ resources = (gcnew System::ComponentModel::ComponentResourceManager(MyForm::typeid));
this->pictureBoxPrevious = (gcnew System::Windows::Forms::PictureBox());
this->pictureBoxCurrent = (gcnew System::Windows::Forms::PictureBox());
this->label1 = (gcnew System::Windows::Forms::Label());
this->label2 = (gcnew System::Windows::Forms::Label());
this->textBoxData = (gcnew System::Windows::Forms::TextBox());
this->label3 = (gcnew System::Windows::Forms::Label());
this->buttonStart = (gcnew System::Windows::Forms::Button());
this->buttonToStart = (gcnew System::Windows::Forms::Button());
this->buttonPrevious = (gcnew System::Windows::Forms::Button());
this->buttonStopAnimation = (gcnew System::Windows::Forms::Button());
this->buttonStartAnimation = (gcnew System::Windows::Forms::Button());
this->buttonNext = (gcnew System::Windows::Forms::Button());
this->buttonToFinish = (gcnew System::Windows::Forms::Button());
this->numericUpDown = (gcnew System::Windows::Forms::NumericUpDown());
this->label4 = (gcnew System::Windows::Forms::Label());
this->comboBox = (gcnew System::Windows::Forms::ComboBox());
this->label5 = (gcnew System::Windows::Forms::Label());
this->timer = (gcnew System::Windows::Forms::Timer(this->components));
this->numericUpDownInterval = (gcnew System::Windows::Forms::NumericUpDown());
this->label6 = (gcnew System::Windows::Forms::Label());
this->labelComment = (gcnew System::Windows::Forms::Label());
this->menuStrip1 = (gcnew System::Windows::Forms::MenuStrip());
this->fileToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());
this->restrictionsToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());
this->directionToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());
this->toolStripMenuItem1 = (gcnew System::Windows::Forms::ToolStripSeparator());
this->exitToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());
this->helpToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());
this->aboutToolStripMenuItem = (gcnew System::Windows::Forms::ToolStripMenuItem());
this->labelRestrict = (gcnew System::Windows::Forms::Label());
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->pictureBoxPrevious))->BeginInit();
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->pictureBoxCurrent))->BeginInit();
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->numericUpDown))->BeginInit();
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->numericUpDownInterval))->BeginInit();
this->menuStrip1->SuspendLayout();
this->SuspendLayout();
//
// pictureBoxPrevious//
this->pictureBoxPrevious->Location = System::Drawing::Point(13, 167);
this->pictureBoxPrevious->Name = L"pictureBoxPrevious";
this->pictureBoxPrevious->Size = System::Drawing::Size(987, 50);
this->pictureBoxPrevious->TabIndex = 0;
this->pictureBoxPrevious->TabStop = false;
this->pictureBoxPrevious->Paint += gcnew System::Windows::Forms::PaintEventHandler(this, &MyForm::pictureBoxPrevious_Paint);
//
// pictureBoxCurrent//
this->pictureBoxCurrent->Location = System::Drawing::Point(13, 257);
this->pictureBoxCurrent->Name = L"pictureBoxCurrent";
this->pictureBoxCurrent->Size = System::Drawing::Size(987, 47);
this->pictureBoxCurrent->TabIndex = 0;
this->pictureBoxCurrent->TabStop = false;
this->pictureBoxCurrent->Paint += gcnew System::Windows::Forms::PaintEventHandler(this, &MyForm::pictureBoxCurrent_Paint);
//
// label1
//
this->label1->AutoSize = true;
this->label1->Location = System::Drawing::Point(9, 139);
this->label1->Name = L"label1";
this->label1->Size = System::Drawing::Size(182, 13);
this->label1->TabIndex = 1;
this->label1->Text = L"Предыдущее состояние масссива";
//
// label2
//
this->label2->AutoSize = true;
this->label2->Location = System::Drawing::Point(10, 231);
this->label2->Name = L"label2";
this->label2->Size = System::Drawing::Size(155, 13);
this->label2->TabIndex = 1;
this->label2->Text = L"Текущее состояние массива";
//
// textBoxData//
this->textBoxData->Anchor = static_cast<System::Windows::Forms::AnchorStyles>(((System::Windows::Forms::AnchorStyles::Top | System::Windows::Forms::AnchorStyles::Left)
| System::Windows::Forms::AnchorStyles::Right));
this->textBoxData->Location = System::Drawing::Point(58, 71);
this->textBoxData->Name = L"textBoxData";
this->textBoxData->Size = System::Drawing::Size(836, 20);
this->textBoxData->TabIndex = 2;
this->textBoxData->Text = L"10 -20 50 -15 18 -14 10 -10 17 -40";
this->textBoxData->Enter += gcnew System::EventHandler(this, &MyForm::textBoxData_Enter);
this->textBoxData->Leave += gcnew System::EventHandler(this, &MyForm::textBoxData_Leave);
//
// label3
//
this->label3->AutoSize = true;
this->label3->Location = System::Drawing::Point(9, 73);
this->label3->Name = L"label3";
this->label3->Size = System::Drawing::Size(46, 13);
this->label3->TabIndex = 1;
this->label3->Text = L"Массив";
//
// buttonStart//
this->buttonStart->Anchor = static_cast<System::Windows::Forms::AnchorStyles>((System::Windows::Forms::AnchorStyles::Top | System::Windows::Forms::AnchorStyles::Right));
this->buttonStart->Location = System::Drawing::Point(912, 71);
this->buttonStart->Name = L"buttonStart";
this->buttonStart->Size = System::Drawing::Size(88, 23);
this->buttonStart->TabIndex = 3;
this->buttonStart->Text = L"Сортировать";
this->buttonStart->UseVisualStyleBackColor = true;
this->buttonStart->Click += gcnew System::EventHandler(this, &MyForm::buttonStart_Click);
//
// buttonToStart//
this->buttonToStart->Location = System::Drawing::Point(61, 97);
this->buttonToStart->Name = L"buttonToStart";
this->buttonToStart->Size = System::Drawing::Size(32, 23);
this->buttonToStart->TabIndex = 4;
this->buttonToStart->Text = L"|<";
this->buttonToStart->UseVisualStyleBackColor = true;
this->buttonToStart->Click += gcnew System::EventHandler(this, &MyForm::buttonToStart_Click);
//
// buttonPrevious//
this->buttonPrevious->Location = System::Drawing::Point(99, 97);
this->buttonPrevious->Name = L"buttonPrevious";
this->buttonPrevious->Size = System::Drawing::Size(32, 23);
this->buttonPrevious->TabIndex = 4;
this->buttonPrevious->Text = L"<";
this->buttonPrevious->UseVisualStyleBackColor = true;
this->buttonPrevious->Click += gcnew System::EventHandler(this, &MyForm::buttonPrevious_Click);
//
// buttonStopAnimation//
this->buttonStopAnimation->Enabled = false;
this->buttonStopAnimation->Location = System::Drawing::Point(374, 97);
this->buttonStopAnimation->Name = L"buttonStopAnimation";
this->buttonStopAnimation->Size = System::Drawing::Size(73, 23);
this->buttonStopAnimation->TabIndex = 4;
this->buttonStopAnimation->Text = L"Стоп";
this->buttonStopAnimation->UseVisualStyleBackColor = true;
this->buttonStopAnimation->Click += gcnew System::EventHandler(this, &MyForm::button5_Click);
//
// buttonStartAnimation//
this->buttonStartAnimation->Location = System::Drawing::Point(300, 97);
this->buttonStartAnimation->Name = L"buttonStartAnimation";
this->buttonStartAnimation->Size = System::Drawing::Size(68, 23);
this->buttonStartAnimation->TabIndex = 4;
this->buttonStartAnimation->Text = L"Пуск";
this->buttonStartAnimation->UseVisualStyleBackColor = true;
this->buttonStartAnimation->Click += gcnew System::EventHandler(this, &MyForm::button6_Click);
//
// buttonNext//
this->buttonNext->Location = System::Drawing::Point(191, 97);
this->buttonNext->Name = L"buttonNext";
this->buttonNext->Size = System::Drawing::Size(32, 23);
this->buttonNext->TabIndex = 4;
this->buttonNext->Text = L">";
this->buttonNext->UseVisualStyleBackColor = true;
this->buttonNext->Click += gcnew System::EventHandler(this, &MyForm::buttonNext_Click);
//
// buttonToFinish//
this->buttonToFinish->Location = System::Drawing::Point(229, 97);
this->buttonToFinish->Name = L"buttonToFinish";
this->buttonToFinish->Size = System::Drawing::Size(32, 23);
this->buttonToFinish->TabIndex = 4;
this->buttonToFinish->Text = L">|";
this->buttonToFinish->UseVisualStyleBackColor = true;
this->buttonToFinish->Click += gcnew System::EventHandler(this, &MyForm::buttonToFinish_Click);
//
// numericUpDown//
this->numericUpDown->Location = System::Drawing::Point(137, 100);
this->numericUpDown->Name = L"numericUpDown";
this->numericUpDown->Size = System::Drawing::Size(48, 20);
this->numericUpDown->TabIndex = 6;
this->numericUpDown->TextAlign = System::Windows::Forms::HorizontalAlignment::Right;
this->numericUpDown->ValueChanged += gcnew System::EventHandler(this, &MyForm::numericUpDown_ValueChanged);
//
// label4
//
this->label4->AutoSize = true;
this->label4->Location = System::Drawing::Point(14, 312);
this->label4->Name = L"label4";
this->label4->Size = System::Drawing::Size(70, 13);
this->label4->TabIndex = 7;
this->label4->Text = L"Примечание";
//
// comboBox//
this->comboBox->FormattingEnabled = true;
this->comboBox->Items->AddRange(gcnew cli::array< System::Object^ >(2) { L"Перемешиванием (Shaker)", L"Расческой (Comb)" });
this->comboBox->Location = System::Drawing::Point(108, 35);
this->comboBox->Name = L"comboBox";
this->comboBox->Size = System::Drawing::Size(162, 21);
this->comboBox->TabIndex = 8;
//
// label5
//
this->label5->AutoSize = true;
this->label5->Location = System::Drawing::Point(14, 38);
this->label5->Name = L"label5";
this->label5->Size = System::Drawing::Size(88, 13);
this->label5->TabIndex = 1;
this->label5->Text = L"Вид сортировки";
//
// timer
//
this->timer->Interval = 500;
this->timer->Tick += gcnew System::EventHandler(this, &MyForm::timer_Tick);
//
// numericUpDownInterval//
this->numericUpDownInterval->Increment = System::Decimal(gcnew cli::array< System::Int32 >(4) { 100, 0, 0, 0 });
this->numericUpDownInterval->Location = System::Drawing::Point(593, 100);
this->numericUpDownInterval->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 3000, 0, 0, 0 });
this->numericUpDownInterval->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 100, 0, 0, 0 });
this->numericUpDownInterval->Name = L"numericUpDownInterval";
this->numericUpDownInterval->Size = System::Drawing::Size(105, 20);
this->numericUpDownInterval->TabIndex = 6;
this->numericUpDownInterval->TextAlign = System::Windows::Forms::HorizontalAlignment::Right;
this->numericUpDownInterval->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) { 500, 0, 0, 0 });
this->numericUpDownInterval->ValueChanged += gcnew System::EventHandler(this, &MyForm::numericUpDown1_ValueChanged);
//
// label6
//
this->label6->AutoSize = true;
this->label6->Location = System::Drawing::Point(475, 102);
this->label6->Name = L"label6";
this->label6->Size = System::Drawing::Size(112, 13);
this->label6->TabIndex = 1;
this->label6->Text = L"Пауза при анимации";
//
// labelComment//
this->labelComment->AutoSize = true;
this->labelComment->Location = System::Drawing::Point(87, 312);
this->labelComment->Name = L"labelComment";
this->labelComment->Size = System::Drawing::Size(44, 13);
this->labelComment->TabIndex = 7;
this->labelComment->Text = L"Начало";
//
// menuStrip1
//
this->menuStrip1->Items->AddRange(gcnew cli::array< System::Windows::Forms::ToolStripItem^ >(2) {
this->fileToolStripMenuItem,
this->helpToolStripMenuItem});
this->menuStrip1->Location = System::Drawing::Point(0, 0);
this->menuStrip1->Name = L"menuStrip1";
this->menuStrip1->Size = System::Drawing::Size(1016, 24);
this->menuStrip1->TabIndex = 9;
this->menuStrip1->Text = L"menuStrip1";
//
// fileToolStripMenuItem//
this->fileToolStripMenuItem->DropDownItems->AddRange(gcnew cli::array< System::Windows::Forms::ToolStripItem^ >(4) {
this->restrictionsToolStripMenuItem,
this->directionToolStripMenuItem, this->toolStripMenuItem1, this->exitToolStripMenuItem});
this->fileToolStripMenuItem->Name = L"fileToolStripMenuItem";
this->fileToolStripMenuItem->Size = System::Drawing::Size(45, 20);
this->fileToolStripMenuItem->Text = L"Файл";
//
// restrictionsToolStripMenuItem//
this->restrictionsToolStripMenuItem->Checked = true;
this->restrictionsToolStripMenuItem->CheckState = System::Windows::Forms::CheckState::Checked;
this->restrictionsToolStripMenuItem->Name = L"restrictionsToolStripMenuItem";
this->restrictionsToolStripMenuItem->Size = System::Drawing::Size(177, 22);
this->restrictionsToolStripMenuItem->Text = L"Ограничения";
this->restrictionsToolStripMenuItem->Click += gcnew System::EventHandler(this, &MyForm::restrictionsToolStripMenuItem_Click);
//
// directionToolStripMenuItem//
this->directionToolStripMenuItem->Name = L"directionToolStripMenuItem";
this->directionToolStripMenuItem->Size = System::Drawing::Size(177, 22);
this->directionToolStripMenuItem->Text = L"В обратном порядке";
this->directionToolStripMenuItem->Click += gcnew System::EventHandler(this, &MyForm::directionToolStripMenuItem_Click);
//
// toolStripMenuItem1
//
this->toolStripMenuItem1->Name = L"toolStripMenuItem1";
this->toolStripMenuItem1->Size = System::Drawing::Size(174, 6);
//
// exitToolStripMenuItem//
this->exitToolStripMenuItem->Name = L"exitToolStripMenuItem";
this->exitToolStripMenuItem->Size = System::Drawing::Size(177, 22);
this->exitToolStripMenuItem->Text = L"Выход";
this->exitToolStripMenuItem->Click += gcnew System::EventHandler(this, &MyForm::exitToolStripMenuItem_Click);
//
// helpToolStripMenuItem//
this->helpToolStripMenuItem->DropDownItems->AddRange(gcnew cli::array< System::Windows::Forms::ToolStripItem^ >(1) { this->aboutToolStripMenuItem });
this->helpToolStripMenuItem->Name = L"helpToolStripMenuItem";
this->helpToolStripMenuItem->Size = System::Drawing::Size(59, 20);
this->helpToolStripMenuItem->Text = L"Помощь";
//
// aboutToolStripMenuItem//
this->aboutToolStripMenuItem->Name = L"aboutToolStripMenuItem";
this->aboutToolStripMenuItem->Size = System::Drawing::Size(138, 22);
this->aboutToolStripMenuItem->Text = L"О программе";
this->aboutToolStripMenuItem->Click += gcnew System::EventHandler(this, &MyForm::aboutToolStripMenuItem_Click);
//
// labelRestrict//
this->labelRestrict->AutoSize = true;
this->labelRestrict->Location = System::Drawing::Point(285, 55);
this->labelRestrict->Name = L"labelRestrict";
this->labelRestrict->Size = System::Drawing::Size(570, 13);
this->labelRestrict->TabIndex = 10;
this->labelRestrict->Text = L"Диапазон чисел ограничен [-999..999]. Количество ограничено 20. Для снятия ограни"
L"чений используйте меню";
this->labelRestrict->Visible = false;
//
// MyForm//
this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);
this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
this->ClientSize = System::Drawing::Size(1016, 369);
this->Controls->Add(this->labelRestrict);
this->Controls->Add(this->comboBox);
this->Controls->Add(this->labelComment);
this->Controls->Add(this->label4);
this->Controls->Add(this->numericUpDownInterval);
this->Controls->Add(this->numericUpDown);
this->Controls->Add(this->buttonToFinish);
this->Controls->Add(this->buttonNext);
this->Controls->Add(this->buttonStartAnimation);
this->Controls->Add(this->buttonStopAnimation);
this->Controls->Add(this->buttonPrevious);
this->Controls->Add(this->buttonToStart);
this->Controls->Add(this->buttonStart);
this->Controls->Add(this->textBoxData);
this->Controls->Add(this->label2);
this->Controls->Add(this->label5);
this->Controls->Add(this->label6);
this->Controls->Add(this->label3);
this->Controls->Add(this->label1);
this->Controls->Add(this->pictureBoxCurrent);
this->Controls->Add(this->pictureBoxPrevious);
this->Controls->Add(this->menuStrip1);
this->Icon = (cli::safe_cast<System::Drawing::Icon^>(resources->GetObject(L"$this.Icon")));
this->MainMenuStrip = this->menuStrip1;
this->Name = L"MyForm";
this->Text = L"Сортировки";
this->Load += gcnew System::EventHandler(this, &MyForm::MyForm_Load);
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->pictureBoxPrevious))->EndInit();
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->pictureBoxCurrent))->EndInit();
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->numericUpDown))->EndInit();
(cli::safe_cast<System::ComponentModel::ISupportInitialize^>(this->numericUpDownInterval))->EndInit();
this->menuStrip1->ResumeLayout(false);
this->menuStrip1->PerformLayout();
this->ResumeLayout(false);
this->PerformLayout();
}
#pragma endregionarray<int>^ A = nullptr; //Массив с даннымиHistory^ H = gcnew History(); //История выполненияprivate: System::Void MyForm_Load(System::Object^ sender, System::EventArgs^ e) {
comboBox->SelectedIndex = 0; //Выбрать сортировкуbuttonStart_Click(sender, e);//Выполнить сортировку}
//Прочитать данные в массив "a"
bool ReadData()
{
//Применить ограничения на исходные данные
//Ограничение по значению - трехзначные положительные числа
//Ограничение по количеству элементов - не более 20
bool Restrictions = restrictionsToolStripMenuItem->Checked;
array<String^>^ separator = { " " };
array<String^>^ d = textBoxData->Text->Split
(separator, System::StringSplitOptions::RemoveEmptyEntries);
A = gcnew array<int>(d->Length);
if (Restrictions && A->Length > 20)
{
MessageBox::Show("Элементов не должно быть больше 20");
return false;
}
for (int i = 0; i < A->Length; i++)
{
if (!int::TryParse(d[i], A[i]))
{
MessageBox::Show(d[i], "Не целое число",
System::Windows::Forms::MessageBoxButtons::OK,
System::Windows::Forms::MessageBoxIcon::Error);
return false;
}
if (Restrictions && (A[i] < -999 || A[i]>999))
{
MessageBox::Show("Элемент " + A[i].ToString() + " меньше -999 или больше 999");
return false;
}
}
return true;
}
//Кнопка "Сортировать"
private: System::Void buttonStart_Click(System::Object^ sender, System::EventArgs^ e)
{
//Прочитать данныеif (!ReadData()) return;
H->Clear();
H->Add(A, "Начало", nullptr);
//Применить сортировкуif (comboBox->SelectedIndex == 0)
ShakerSort(directionToolStripMenuItem->Checked);
elseCombSort(directionToolStripMenuItem->Checked);
H->Add(A, "Конец", nullptr);
//Подготовить параметры вывода
numericUpDown->Minimum = 1;
numericUpDown->Maximum = H->Count - 1;
numericUpDown->Value = 1;
//Обновить изображениеnumericUpDown_ValueChanged(sender, e);
}
/*
*/
//Обменять местами два елемента void Swap(int index1, int index2)
{
int Temp = A[index1];
A[index1] = A[index2];
A[index2] = Temp;
List<int>^ mark = gcnew List<int>();
mark->Add(index1);
mark->Add(index2);
H->Add(A,
"Обмен " +
"A[" + index1.ToString() + "]" +
" и " +
"A[" + index2.ToString() + "]",
mark );
}
void ShakerSort(bool inverse)
{
int N = A->Length; //Длина массива int left = 0;
int right = N - 1;
bool flag = true;
while (left <= right && flag)
{
flag = false;
for (int i = left; i < right; i++) {
if ((A[i] > A[i + 1]) ^ inverse)
{
Swap(i, i + 1);
flag = true;
}
}
right--;
for (int i = right; i > left; i--) {
if ((A[i] < A[i - 1]) ^ inverse) {
Swap(i, i - 1);
flag = true;
}
}
left++;
}
}
void CombSort(bool inverse)
{
//!!
int N = A->Length; //Длина массива double fakt = 1.2473309; // фактор уменьшения double step = N - 1;
while (step >= 1)
{
for (int i = 0; i + (int)step < N; ++i)
{
if ((A[i] > A[i + (int)step]) ^ inverse)
Swap(i, i + (int)step);
}
step /= fakt;
}
// сортировка пузырьком того, что осталось
for (int i = 0; i < N - 1; i++)
{
bool swapped = false;
for (int j = 0; j < N - i - 1; j++)
{
if ((A[j] > A[j + 1]) ^ inverse) {
Swap(j, j + 1);
swapped = true;
}
}
if (!swapped) break;
}
}
private: System::Void numericUpDown_ValueChanged(System::Object^ sender, System::EventArgs^ e)
{
//Обновить изображенияpictureBoxCurrent->Refresh();
pictureBoxPrevious->Refresh();
}
private: System::Void buttonToStart_Click(System::Object^ sender, System::EventArgs^ e)
{
numericUpDown->Value = numericUpDown->Minimum;
}
private: System::Void buttonPrevious_Click(System::Object^ sender, System::EventArgs^ e) {
if (numericUpDown->Value > numericUpDown->Minimum)
numericUpDown->Value--;
}
private: System::Void buttonNext_Click(System::Object^ sender, System::EventArgs^ e) {
if (numericUpDown->Value < numericUpDown->Maximum)
numericUpDown->Value++;
}
private: System::Void buttonToFinish_Click(System::Object^ sender, System::EventArgs^ e) {
numericUpDown->Value = numericUpDown->Maximum;
}
private: System::Void numericUpDown1_ValueChanged(System::Object^ sender, System::EventArgs^ e) {
timer->Interval = (int)numericUpDownInterval->Value;
}
//Стоп анимацияprivate: System::Void button5_Click(System::Object^ sender, System::EventArgs^ e) {
buttonStartAnimation->Enabled = true;
buttonStopAnimation->Enabled = false;
timer->Enabled = false;
}
//Пуск анимацияprivate: System::Void button6_Click(System::Object^ sender, System::EventArgs^ e) {
buttonStartAnimation->Enabled = false;
buttonStopAnimation->Enabled = true;
//Если в конце - то с начала
if (numericUpDown->Value == numericUpDown->Maximum)
numericUpDown->Value = numericUpDown->Minimum;
timer->Enabled = true;
}
private: System::Void timer_Tick(System::Object^ sender, System::EventArgs^ e)
{
buttonNext_Click(sender, e);
if (numericUpDown->Value == numericUpDown->Maximum)
button5_Click(sender, e);
}
private: System::Void pictureBoxPrevious_Paint(System::Object^ sender, System::Windows::Forms::PaintEventArgs^ e)
{
//Вывести предыдущее состояние массива
//Индекс элемента истории
int index = (int)numericUpDown->Value - 1;
//сам элементElement^ element = H->Get(index);
//вывести на заданное полотно
//sender - соответствующий pictureBoxelement->Paint(e->Graphics, ((PictureBox^)sender)->Width, ((PictureBox^)sender)->Height);
}
private: System::Void pictureBoxCurrent_Paint(System::Object^ sender, System::Windows::Forms::PaintEventArgs^ e) {
//Вывести текущее состояние массиваint index = (int)numericUpDown->Value;
Element^ element = H->Get(index);
element->Paint(e->Graphics, ((PictureBox^)sender)->Width, ((PictureBox^)sender)->Height);
labelComment->Text = element->comment;
}
//О прог?