МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ БЕЛАРУСЬ
БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Факультет информационных технологий и робототехники (ФИТР)
Кафедра программного обеспечения вычислительной техники
и автоматизированных систем
КУРСОВАЯ РАБОТА
по дисциплине: “Языки программирования”
на тему: ” Сортировка массива структур на основе структуры
" Магазин” ”
Выполнил: ст. гр. 10702214 Нгуен Зуй Туан Ань
Приняла: ст. преподаватель И.М. Желакович
Минск 2015
Белорусский национальный технический университет
Кафедра программного обеспечения вычислительной техники
и автоматизированных систем
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту (работе)
по дисциплине “языки программирования”
на тему: ” Сортировка массива структур на основе структуры
" Магазин” ”
Исполнитель:_______ Нгуен Зуй Туан Ань
Студент 1 курса, группы 107314
Руководитель:_____Желакович И.М.
Минск 2015
СОДЕРЖАНИЕ
Белорусский национальный технический университет. 2
1. ВВЕДЕНИЕ. 5
2. ТЕОРЕТИЧЕСКИЙ ВОПРОС Дисковые алгоритмы-планировщики. 6
2.1 Алгоритм лифта (англ.) — дисковый алгоритм планирования, который работает как лифт. 6
2.2 Алгоритм кратчайшего перемещения (англ.) — дисковый алгоритм планирования для уменьшения времени поиска. Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков. 6
Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы. 6
Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорирование препятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так: 6
Этот подход прост, так как он предъявляет совсем немного требований: все, что необходимо знать - это относительные положения объекта и его цели, и признак блокирования препятствием. Для многих игровых ситуаций этого достаточно. 6
Различные стратегии обхода препятствий включают в себя: 6
2.2.1 Перемещение в случайном направлении. 6
Если препятствия маленькие и выпуклые, объект (показан зеленой точкой) может, вероятно, обойти их путем небольшого смещения в сторону до тех пор, пока не достигнет цели (показана красной точкой). Рисунок 1А показывает, как работает такая стратегия. Проблемы у этого метода возникают, если препятствия большие или вогнутые, как показано на рисунке 1Б - объект может полностью застрять или как минимум потерять много времени, пока не будет найден обходной путь. Существует только один способ избежать этого: если проблему очень трудно преодолеть, то измените игру так, чтобы эта проблема никогда не возникала. То есть, убедитесь, что в игре никогда не будет вогнутых объектов. 6
2.2.2 Трассировка вокруг препятствия. 6
К счастью, существуют другие методы обхода. Если препятствие большое, можно коснуться рукой препятствия и следовать контуру препятствия, пока она не обойдено. Рисунок 2А показывает, как хорошо этот метод работает с большими препятствиями. Проблема с этим методом состоит в принятии решения - когда же прекратить трассировку. Типичной эвристикой может быть: "Остановить трассировку при передвижении в направлении, которое было желаемым в начале трассировки". Это будет работать во многих случаях, однако рисунок 2Б показывает, как можно постоянно кружить внутри препятствия не находя пути наружу. 7
2.2.3 Надежная трассировка. 7
Более надежная эвристика пришла из работ над мобильными роботами: "При блокировании, вычислить уравнение линии из текущей позиции к цели. Трассировать до тех пор, пока эта линия не пересечена снова. Прервать работу, если вы опять попали в начальную позицию". Этот метод гарантирует нахождение пути вокруг препятствия, если он есть, что показано на рисунке 3А. (Если изначальная точка блокирования между вами и целью при пересечении линии, ни в коем случае не останавливайте трассировку, чтобы избежать дальнейшего зацикливания) Рисунок 3Б показывает обратную сторону этого подхода: зачастую требуется гораздо больше времени на трассировку чем необходимо. Компромисс состоит в комбинации обоих подходов: всегда использовать эвристику попроще для остановки трассирования, но если зафиксировано зацикливание, переключаться на надежную эвристику. 7
3. ПРАКТИЧЕСКИЙ РАЗДЕЛ.. 8
3.1. Математическая формулировка задачи. 8
3.2. Описание программы. 9
3.3. Блок-схема алгоритма: 11
4 Контрольный пример. 12
5. ВЫВОДЫ.. 17
6. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.. 18
7. Приложение А.. 19
8. Приложение B. 31
1. ВВЕДЕНИЕ
Цель курсовой работы - закрепление и углубление знаний, полученных при изучении курса «Основы алгоритмизации и программирования» посредством разработки программного обеспечения на языке С++; нaучитьcя практический применять полеченные теоретический знания пpи решении конкретных вопросов; нaучитьcя пользоваться справочной литературой.
В данной курсовой работе представлены несколько видов сортировок.Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:
· Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее,среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log2 n) операций. При этом число n должно быть заранее известно.
2. ТЕОРЕТИЧЕСКИЙ ВОПРОС Дисковые алгоритмы-планировщики.
2.1 Алгоритм лифта (англ.) — дисковый алгоритм планирования, который работает как лифт.
2.2 Алгоритм кратчайшего перемещения (англ.) — дисковый алгоритм планирования для уменьшения времени поиска. Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков.
Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы.
Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорирование препятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так:
Этот подход прост, так как он предъявляет совсем немного требований: все, что необходимо знать - это относительные положения объекта и его цели, и признак блокирования препятствием. Для многих игровых ситуаций этого достаточно.
Различные стратегии обхода препятствий включают в себя:
2.2.1 Перемещение в случайном направлении
Если препятствия маленькие и выпуклые, объект (показан зеленой точкой) может, вероятно, обойти их путем небольшого смещения в сторону до тех пор, пока не достигнет цели (показана красной точкой). Рисунок 1А показывает, как работает такая стратегия. Проблемы у этого метода возникают, если препятствия большие или вогнутые, как показано на рисунке 1Б - объект может полностью застрять или как минимум потерять много времени, пока не будет найден обходной путь. Существует только один способ избежать этого: если проблему очень трудно преодолеть, то измените игру так, чтобы эта проблема никогда не возникала. То есть, убедитесь, что в игре никогда не будет вогнутых объектов.
2.2.2 Трассировка вокруг препятствия
К счастью, существуют другие методы обхода. Если препятствие большое, можно коснуться рукой препятствия и следовать контуру препятствия, пока она не обойдено. Рисунок 2А показывает, как хорошо этот метод работает с большими препятствиями. Проблема с этим методом состоит в принятии решения - когда же прекратить трассировку. Типичной эвристикой может быть: "Остановить трассировку при передвижении в направлении, которое было желаемым в начале трассировки". Это будет работать во многих случаях, однако рисунок 2Б показывает, как можно постоянно кружить внутри препятствия не находя пути наружу.
2.2.3 Надежная трассировка
Более надежная эвристика пришла из работ над мобильными роботами: "При блокировании, вычислить уравнение линии из текущей позиции к цели. Трассировать до тех пор, пока эта линия не пересечена снова. Прервать работу, если вы опять попали в начальную позицию". Этот метод гарантирует нахождение пути вокруг препятствия, если он есть, что показано на рисунке 3А. (Если изначальная точка блокирования между вами и целью при пересечении линии, ни в коем случае не останавливайте трассировку, чтобы избежать дальнейшего зацикливания) Рисунок 3Б показывает обратную сторону этого подхода: зачастую требуется гораздо больше времени на трассировку чем необходимо. Компромисс состоит в комбинации обоих подходов: всегда использовать эвристику попроще для остановки трассирования, но если зафиксировано зацикливание, переключаться на надежную эвристику.
3. ПРАКТИЧЕСКИЙ РАЗДЕЛ
3.1. Математическая формулировка задачи
Разработать программу, реализующую сортировку массива структур (50 элементов). В качестве элемента массива выбрать структуру, соответствующую индивидуальному варианту. Предусмотреть заполнение массива из файла (подготовить файл на 50 элементов).
Программа должна реализовать не менее 3-х алгоритмов сортировки (на выбор программиста). При этом алгоритм сортировки, направление сортировки (по возрастанию/по убыванию), ключ сортировки (одно или несколько полей) и длину ключа (для текстовых полей) выбирает пользователь. Выполнить сравнительный анализ для различных алгоритмов сортировки (скорость выполнения, количество сравнений, количество перестановок). Отсортированный массив и результаты анализа хранить в текстовых файлах.
Предусмотреть многоуровневое меню:
1) Заполнение массива из файла (выбор файла, тек. папка, любая папка)
2) Выбор алгоритма сортировки
3) Выбор ключевого поля (или нескольких полей – до 3-х)
4) Установка длины ключа (для текстовых полей)
5) Сохранение результата
6) Вывод сравнительного анализа последних сортировок
a) на экран
b) в файл
7) Выход
Описание использованных сортировок:
Сортировка - это процесс перестановки объектов данного множества в определённом порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. Поэтому элементы сортировки присутствуют во многих задачах прикладного программирования.
Пузырьковая сортировка
Этот метод назван так потому, что с каждым циклом самый легкий элемент поднимается вверх списка, подобно пузырьку.
В первом проходе сравниваются попарно элементы: первый – второй, второй – третий, третий – четвертый и т.д. до n-1 – n. Каждый раз в паре самый легкий перемещается вверх. В результате одного прохода самый тяжелый элемент опустится на дно.
Сортировка методом простого выбора
Основные действия алгоритма для сортировки массива длиной L заключаются в следующем:
Для каждого значения индекса i выполнить два действия:
1) Среди элементов с индексами от i до (L-1) найти элемент с минимальным значением (если сортировка производится по возрастанию).
2) Обменять значения i-го и минимального элементов.
Сортировка методом простого включения
В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части.
3.2. Описание программы.
В начале программы пользователю предлагается многоуровневое меню с выбором действий, которые программа выполняет. В первом пункте меню предлагается заполнить массив структурами из файла. При его выборе пользователю будет предложено ввести имя и адрес файла, который будет считан в массив.
При выборе второго пункта меню будет предложен выбор алгоритма сортировки, с помощью которой будет отсортирован массив.
При выборе третьего пункта меню будет предложен выбор ключевого поля, по которому и будет сортироваться массив.
При выборе четвёртого пункта меню на экран выведется количество элементов.
При выборе пятого пункта меню будет предложено сохранить результаты сортировки в файл.
При выборе шестого пункта меню будет предложено вывести сравнительный анализ последних сортировок на экран или записать в файл.
При выборе седьмого пункта меню произойдёт выход из программы.
Подробнее об основных функциях программы.
Функции, использованные в программе:
Здесь будет дано описание функций содержащихся в программе. Сам код программы будет представлен на «Приложении 1».
- Функция «main( )» содержит вызов функции «Меню»;
- Функция «PrintMenu( )» выводит на экран первый уровень меню, где пользователь должен сделать выбор, что делать дальше;
- Функция «Menu( )» содержит остальные уровни меню, с последуюющим вызовом других функций, в зависимости от выбора действий пользователем;
- Функция «Load(string fileName)» используется для считывания массива структур с файл для дальнейших операций с ним;
- Функция «Sort1(boolup)» предназначена для выполнения пузырьковой сортировки;
- Функция «Sort2(boolup)» предназначена для выполнения сортировки методом простого выбора;
- Функция «Sort3(boolup)» предназначена для выполнения сортировки методом простого включения;
- Функция «compare(sotrudnik *a, sotrudnik *b, boolup)» предназначена для сравнения параметров при сортировке;
- Функция «swap(sotrudnik *a, sotrudnik *b)» предназначена для выполнения перестановки при сортировке;
- Функция «SaveResult(stringfileName)» предназначена для сохранения результатов сортировки в файл;
- Функция «SaveSortInfo(stringfileName)» предназначена для сохранения сравнительного анализа последних сортировок в файл;
- Функция «DisplaySortInfo( )» предназначена для вывода сравнительного анализа последних сортировок на экран.
3.3. Блок-схема алгоритма:
4 .Контрольный пример.
При запуске программы на экране появится окно с главным меню, в котором предложены варианты возможных действий программы (рисунок 1).
Рисунок 1 – Вид окна сразу после запуска программы.
При выборе первого пункта меню, будет предложено ввести имя файла (при необходимости и путь) в котором расположен массив структур (рисунок 2, 3 и 4).
Рисунок 2 – Первый пункт, считывание массива структур с файла.
Нажатием любой клавиши, меню обновится. При выборе второго пункта, будет предложен выбор метода сортировки (рисунок 3).
Рисунок 3 – Второй пункт, выполнение сортировки.
Рисунок 4 – Второй пункт, выполнение сортировки.
Рисунок 5 – Второй пункт, выполнение сортировки.
При нажатии любой клавиши, меню обновится. При выборе третьего пункта, будет предложено выбрать ключевое поле (рисунок 4.6).
Рисунок 6 – Выбор ключевого поля.
При нажатии любой клавиши, меню обновится. При выборе четвертого пункта на экран выведется количество элементов (рисунок 7).
Рисунок 4.7 – Четвертый пункт, вывод количества элементов.
При нажатии любой клавиши, меню обновится. При выборе пятого пункта, будет предложено сохранить результаты сортировки в файл (рисунок 8).
Рисунок 8 – Пятый пункт, сохранение результатов в файл.
При нажатии любой клавиши, меню обновится. При выборе шестого пункта, будет предложено вывести сравнительный анализ на экран или в файл(рисунок 9 и 10).
Рисунок 9 – Шестой пункт, вывод сравнительного анализа на экран.
Рисунок 10 – Шестой пункт, вывод сравнительного анализа в файл.
При нажатии любой клавиши, меню обновится. При выборе седьмого пункта, осуществится выход из программы (рисунок 11).
Рисунок 11 – Седьмой пункт, выход из программы.
5. ВЫВОДЫ
В результате работы была написана программа, которая реализует алгоритм очереди как в статическом варианте (на основе массива структур), так и в динамическом. В неё предусмотрены функции добавления и удаления элементов. Программа может считывать данные, как с консоли, так и из файла. Также она может выводить полученный результат и в файл и на консоль. В программе реализован алгоритм обработки исключений. Также в программе реализована обработка ошибочных ситуаций, например переполнение очереди, удаление из пустого дека, вывод элементов пустой очереди и т.п. На практике были закреплены знания по алгоритмическому языку С++, а именно работа с операторами циклов и ветвлений, стандартными функциями ввода-вывода, функциями работы с файлами и строками. Программа не использует временных файлов и поэтому .exe файл может находиться на защищенном от записи носителе, главное правильно указать расположение файла результата.
6. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Уолтер Сэвитч. С++ в примерах. Москва: Эком, 1997.
2. Язык программирования Си. Москва: Производственно-внедренческий кооператив "И Н Т Е Р Ф Е Й С", 1988.
3. Б.В. Керниган,Д.М. Ричи. ЯЗЫК С.
4. В.А. Скляров. Программирование на языках Си и Си++. Мн.: Выш. шк.,1997. - 528с.
5. Страуструп Бьерн. Язык программирования Си++. М.: Софт,1999.
6. Шилд Герберт. - Самоучитель C++ / Герберт Шилдт . - СПб : BHV - Санкт-Петербург, 1997. - 511 с.
7. Nixon M., Aguado A. Feature extraction and image processing // Newnes, 2002, p. 350.
7. Приложение А
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using namespace boost;
int
kolich=0;
//переменная
для подсчета количества элементов
string Par1 = "Номер", Par2; //параметр, отображающий установленную сортировку
long Time1, Time2, Time3; //время сортировки
using boost::chrono::high_resolution_clock;
using boost::chrono::nanoseconds;
struct Shop
//структура
{
int num; //номер (ключ)
string name; //Название
string fio; //ФИО директора
int kol; //Количество сотрудников
int dohod; //Годовой доход
};
Shop
mass[50];
//объявление
массива структур
byte index = 0; //начальное значение индекса
void swap(Shop *a, Shop *b) //своп структуры
{
auto t = a;
a = b;
b = t;
}
bool compare(Shop *a, Shop *b, bool up) //сравнивание параметров при сортировке
{
if (index == 0) // номер (ключ)
{
Par1 = "Номер";
auto v1 = a->num;
auto v2 = b->num;
if (up ?
(v1 > v2) : (v1 < v2)) //если
соритировка по убыванию то (v1>v2), иначе (v1 { return true; } else { return false; } } if
(index == 1) //
Название { Par1 = "Название
магазина: "; auto v1 = a->name; auto v2 = b->name; if (up ? (v1
> v2) : (v1 < v2)) //если соритировка по
убыванию то (v1>v2), иначе (v1 { return true; } else { return false; } } if
(index == 2) //
Фамилия Имя директора { Par1 = "Фамилия
Имя директора: "; auto v1 =
a->fio; auto v2 = b->fio; if (up ? (v1
> v2) : (v1 < v2)) //если соритировка по
убыванию то (v1>v2), иначе (v1 { return true; } else { return false; } } if
(index == 3) //Количество
сотрудников { Par1 = "Количество
сотрудников :"; auto v1 = a->kol; auto v2 = b->kol; if (up ? (v1
> v2) : (v1 < v2)) //если соритировка по
убыванию то (v1>v2), иначе (v1 { return true; } else { return false; } } if (index == 4) // Доход { Par1 = "Доход: "; auto v1 = a->dohod; auto v2 = b->dohod; if (up ? (v1
> v2) : (v1 < v2)) //если соритировка по
убыванию то (v1>v2), иначе (v1 { return true; } else { return false; } } } void
Load(string fileName) //загрузка файла { ifstream
file; //объявленеие
переменной для файла file.open(fileName); //открытие файла if (!file) { cout << "Неверное имя файла " << fileName << endl; return; } kolich = 0; for (int i =
0; i < 50; i++) //очистка массива { mass[i].num =
0; mass[i].name = ""; mass[i].fio = ""; mass[i].kol =
0; mass[i].dohod =
0; } while (!file.eof()) //чтение файла { string str; getline(file,
str); mass[kolich].num
= atoi(str.c_str()); //чтение номера getline(file,
mass[kolich].name); //чтение названия getline(file,
mass[kolich].fio); //чтение ФИ getline(file,
str); mass[kolich].kol
= atoi(str.c_str()); //чтение количества сотрудников getline(file,
str); mass[kolich].dohod
= atoi(str.c_str()); //чтение дохода kolich =
kolich++; } cout << "Файл " << fileName
<< " загружен" << endl; } void
SaveResult(string fileName) //сохранение
результата сортировок { if
(kolich == 0) //если в списке нет данных { cout << "Данных
нет в списке!" << endl; return; } ofstream file(fileName); if (!file) { cout << "Неверное имя файла " << fileName << endl;; exit(1); } if
(kolich != 0) //если в списке есть данные { if
(Par2 != "") { file
<< "Сортировка списка: " << Par2
<< endl; file
<< "Ключевое поле: " << Par1
<< endl; } else { file
<< "Список не отсортирован!" << endl; } for (int i =
0; i < kolich; i++) { file
<< mass[i].num << endl; file
<< mass[i].name << endl; file
<< mass[i].fio << endl; file
<< mass[i].kol << endl; file
<< mass[i].dohod << endl; file
<< endl; } } file.close(); cout << "Файл " << fileName
<< " сохранен" << endl; } void
SaveSortInfo(string fileName) //сохранение
информации по времени сортировок { if
(kolich == 0) { cout << "Данных
нет в списке!" << endl; return; } ofstream file(fileName); if (!file) { cout << "Неверное имя файла " << fileName << endl;; exit(1); } else { if ((Time1 == 0) && (Time2 == 0) &&
(Time3 == 0)) { file
<< "Список не отсортирован!"
<< endl; } else { file
<< "Время сортировок в наносекундах:"
<< endl; if (Time1 != 0) { file
<< "1)пузырьковая сортировка = "
<< Time1 << endl; } else { file
<< "Структуры не сортировалась пузырьковой
сортировкой!" << endl; } if
(Time2 != 0) { file
<< "2)методом простого выбора = "
<< Time2 << endl; } else { file
<< "Структуры не сортировалась методом простого
выбора!" << endl; } if
(Time3 != 0) { file
<< "3)методом простого включения = "
<< Time3 << endl; } else { file
<< "Структуры не сортировалась методом простого
включения!" << endl; } } } file.close(); cout << "Файл
" << fileName << "
сохранен" << endl; } void
DisplaySortInfo() { if
(kolich == 0) { cout << "Список
пустой!" << endl; return; } else { if ((Time1 == 0) && (Time2 == 0) &&
(Time3 == 0)) { cout
<< "Список не отсортирован!"
<< endl; } else { cout
<< "Время сортировок в наносекундах:"
<< endl; if
(Time1 != 0) { cout
<< "1)пузырьковая сортировка = "
<< Time1 << endl; } else { cout
<< "Структуры не сортировалась пузырьковой
сортировкой!" << endl; } if
(Time2 != 0) { cout
<< "2)методом простого выбора = "
<< Time2 << endl; } else { cout
<< "Структуры не сортировалась методом простого
выбора!" << endl; } if
(Time3 != 0) { cout
<< "3)методом простого включения = "
<< Time3 << endl; } else { cout
<< "Структуры не сортировалась методом простого
включения!" << endl; } } } } void
Sort1(bool up) { Par2 = up ? ("по
убыванию") : ("по возрастанию"); if
(kolich == 0) //если
список пуст { cout << "Список пуст!" << endl; return; } if
(kolich == 1) //если
в списке 1 элемент { cout << "В
списке 1 элемент!" << endl; return; } auto t0 = high_resolution_clock::now(); //счетчик времени int i, j; for (i = kolich - 1; i > 0; i--) //проходы элементов { for (j = 0; j < i; j++) { if (compare(mass + j, mass + j + 1, up))
//сравнивание текущего и следущего элемента { swap(mass[j],
mass[j + 1]); //обмен элементов } } } Sleep(1); auto t1 = high_resolution_clock::now(); nanoseconds total_ms =
boost::chrono::duration_cast Time1 =
total_ms.count(); cout << "Структуры отсортированы" << endl; } void
Sort2(bool up) { Par2 = up ? ("по
убыванию") : ("по возрастанию"); if
(kolich == 0) //если
список пуст { cout << "Список пуст!" << endl; return; } if
(kolich == 1) //если
в списке 1 элемент { cout << "В
списке 1 элемент!" << endl; return; } auto t0 = high_resolution_clock::now(); int i, j; for (i = 0; i < kolich; i++) //цикл проходов, i -
номер прохода { auto temp = mass[i]; for (j = i - 1; j >= 0 && (compare(mass +
j, &temp, up)); j--) //поиск места элемента { mass[j +
1] = mass[j]; //сдвигаем
элемент вправо, пока не дошли } mass[j + 1] =
temp; //вставить
элемент } Sleep(1); auto t1 = high_resolution_clock::now(); nanoseconds total_ms =
boost::chrono::duration_cast Time2 =
total_ms.count(); cout << "Структуры отсортированы" << endl; } void
Sort3(bool up) { Par2 = up ? ("по
убыванию") : ("по возрастанию"); if
(kolich == 0) //если
список пуст { cout << "Список пуст!" << endl; return; } if
(kolich == 1) //если
в списке 1 элемент { cout << "В
списке 1 элемент!" << endl; return; } auto t0 = high_resolution_clock::now(); //счетчик времени int i, j, min; for (i = 0; i < kolich - 1; i++) { min =
i; //устанавливаем
начальное значение минимального индекса for (j =
i + 1; j < kolich; j++) //находим
минимальный индекс элемента { if (compare(mass + j, mass + min, up)) { min
= j; //меняем
значения местами } } swap(mass[i],
mass[min]); //обмен элементов } Sleep(1); auto t1 = high_resolution_clock::now(); //время выполнения сортировки nanoseconds total_ms =
boost::chrono::duration_cast Time3 =
total_ms.count(); cout << "Структуры отсортированы" << endl; } void
PrintMenu() //Меню { cout<<"Введите
номер пункта, соответствующего вашему выбору: "< cout<<"___________________________________________________________"< cout<<"|
1 |Заполнение массива из файла |"< cout<<"|-----|---------------------------------------------------|"< cout<<"|
2 |Выбор алгоритма сортировки |"< cout<<"|-----|---------------------------------------------------|"< cout<<"|
3 |Выбор ключевого поля |"< cout<<"|-----|---------------------------------------------------|"< cout<<"|
4 |Вывод количества элементов |"< cout<<"|-----|---------------------------------------------------|"< cout<<"|
5 |Сохранение результата |"< cout<<"|-----|---------------------------------------------------|"< cout<<"|
6 |Вывод сравнительного анализа последних сортировок |"< cout<<"|-----|---------------------------------------------------|"< cout<<"|
7 |Выход |"< cout<<"|_____|___________________________________________________|"< } void
Menu() { int v=0; //переменная
выбора пункта меню int w=0; //переменная
выбора подпункта меню do { PrintMenu(); cin>>v; switch(v) { case 1: //Заполнение
списка из файла (выбор файла, тек. папка, любая папка) { cout
<< "Введите имя файла, при необходимости с путём"
<< endl; string fileName; cin
>> fileName; Load(fileName); //загрузка файла getch(); //задержка экрана std::system("cls"); //очистка экрана break; } case 2: //Выбор
алгоритма сортировки { cout<<"Выберите
алгоритм сортировки: "< cout<<"1/2.
Пузырьковая сортировка (по возрастанию/по убыванию)"< cout<<"3/4.
Сортировка методом простого выбора (по возрастанию/по убыванию)"< cout<<"5/6.
Сортировка методом простого включения (по возрастанию/по убыванию)"< cin>>w; switch(w) { case 1: { cout
<< "Пузырьковая сортировка по возрастанию" << endl; Sort1(false); getch(); std::system("cls"); break; } case 2: { cout
<< "Пузырьковая сортировка по убыванию" << endl; Sort1(true); getch(); std::system("cls"); break; } case 3: { cout
<< "Сортировка методом простого выбора по возрастанию"
<< endl; Sort2(false); getch(); std::system("cls"); break; } case 4: { cout
<< "Сортировка методом простого выбора по убыванию" << endl; Sort2(true); getch(); std::system("cls"); break; } case 5: { cout
<< "Сортировка методом простого включения по
возрастанию" << endl; Sort3(false); getch(); std::system("cls"); break; } case 6: { cout
<< "Сортировка методом простого включения по убыванию"
<< endl; Sort3(true); getch(); std::system("cls"); break; } } break; } case 3: //Выбор
ключевого поля (или нескольких полей – до 3-х) { cout<<"Выберите
ключевое поле: "< cout<<"1. Номер (ключ)"< cout<<"2. Название магазина"< cout<<"3.
ФИ директора"< cout<<"4.
Количество сотрудников"< cout<<"5.
Доход"< cin>>w; switch (w) { case 1: { cout
<< "Выбрано ключевое поле [Номер (ключ)] "
<< endl; index = 0; getch(); std::system("cls"); break; } case 2: { cout
<< "Выбрано ключевое поле [Название магазина] "
<< endl; index = 1; getch(); std::system("cls"); break; } case 3: { cout
<< "Выбрано ключевое поле [ФИ директора] "
<< endl; index = 2; getch(); std::system("cls"); break; } case 4: { cout
<< "Выбрано ключевое поле [Количество сотрудников] "
<< endl; index = 3; getch(); std::system("cls"); break; } case 5: { cout
<< "Выбрано ключевое поле [Доход] "
<< endl; index = 4; getch(); std::system("cls"); break; } } break; } case 4: //Вывод
количества элементов в списке { cout
<< "в списке " << kolich << "
элемента/ов" << endl; getch(); std::system("cls"); break; } case 5: //Вывод
результата (на экран/в файл) { cout
<< "Введите имя файла, при необходимости с путём"
<< endl; string fileName; cin
>> fileName; SaveResult(fileName); getch(); std::system("cls"); break; } case 6: //Вывод
сравнительного анализа последних сортировок (на экран/в файл) { cout<<"1.Вывод
сравнительного анализа последних сортировок на экран"< cout<<"2.Вывод
сравнительного анализа последних сортировок в файл"< cin>>w; switch (w) { case 1: { DisplaySortInfo(); getch(); std::system("cls"); break; } case 2: { cout
<< "Введите имя файла, при необходимости с путём"
<< endl; string fileName; cin
>> fileName; SaveSortInfo(fileName); getch(); std::system("cls"); break; } } break; } case 7: //Выход { break; } default: { cout
<< "Некоректный выбор" << endl; getch(); std::system("cls"); break; } } } while(v!=7); } int
main() { setlocale(LC_CTYPE, "Russian"); Menu(); return 0; }
//вывод
информации по времени сортировок на экран
//пузырьковая
сортировка
//время выполнения сортировки
//сортировка
методом простого выбора
//счетчик времени
//время выполнения сортировки
//cортировка
методом простого включения
//Управление
меню
//Главная
функция программы
//вызов меню