Размещено на http://www.allbest.ru/

3

Размещено на http://www.allbest.ru/

Приднестровский государственный университет им. Т.Г. Шевченко

Рыбницкий филиал

Кафедра физики, математики и информатики

Курсовая работа

по дисциплине «Программирование на языке высокого уровня C++»

на тему

Анализ некоторых видов сортировок

Выполнил:

Лученецкий Роман

Рыбница

2012 г.

Введение

В данной курсовой работе рассмотрены некоторые виды сортировок: вставками, выбором, пузырьком, пирамидальная.

Определим понятие "сортировка" как упорядочение элементов некоторой последовательности (например массивов или динамических списков) в возрастающем или убывающем порядке (в случае равных элементов правильнее сказать - в неубывающем и невозрастающем порядке соответственно). Так мы не будем путать определения в будущем.

Для чего нужна сортировка? Очевидно, что если само понятие содержит слово "упорядочение", то сортировка нужна для создание некого порядка среди данных. Искать же что-либо становиться гораздо удобнее, если мы знаем, где это искать, т.е. порядок расположения. Итак, первое приложение сортировки - создание удобных условий для быстрого поиска данных.

Следующая задача является классической: "Сколько в массиве находиться одинаковых элементов каждого типа?" Допустим, что у нас есть массив анкет о сотрудниках организации и нам надо найти их распределение возрастов (сколько человек имеют 30, 50, 60 лет). Эту задачу легко решить, если отсортировать анкеты по возрасту сотрудников, и затем пройтись по массиву, подсчитывая количество сотрудников с каждым возрастом.

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки -- облегчить последующий поиск элементов в отсортированном множестве.

В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонных книгах, в ведомостях по­доходных налогов, в оглавлениях, в библиотеках, в словарях, на складах, да и почти всюду, где их нужно разыскивать. Даже маленьких детей приучают приводить вещи «в порядок», и они сталкиваются с некоторым видом сортировки задолго до того, как узнают что-либо об арифметике.

Сортировки обычно разделяют на две категории: сортировка массивов и сортировка последовательных файлов. Их часто называют внутренней и внешней сортировкой, так, как массивы располагаются во внутренней памяти ЭВМ, а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающих устройствах с механическим передвижением (дисках, лентах).

Цель: исследовать некоторые методы сортировок.

Задачи: изучить литературу по алгоритмам сортировок, составить подпрограммы сортировок, провести анализ и вычислить среднее время каждой сортировки, составить графическое меню.

сортировка алгоритм последовательность подпрограмма

Теоретический раздел

Сортировка пузырьком

Сортировка простыми обменами, сортиромвка пузырькомм (англ. bubble sort) -- простой алгоритм сортировки. Для понимания и реализации этот алгоритм -- простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n?).

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает -- массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

Обратите внимание, что количество повторов во внутреннем цикле уменьшается с каждой итерацией внешнего цикла. Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент будет находиться на N-1 месте. И так далее. Таким образом нет необходимости "обходить" весь массив от начала до конца каждый раз.

Анализ сортировки

При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худшем случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.

Сортировка вставками

Сортировка вставками -- простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

1.эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

2.эффективен на наборах данных, которые уже частично отсортированы;

это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

3.может сортировать список по мере его получения;

использует O(1) временной памяти, включая стек.

Минусом же является высокая сложность алгоритма

Описание:

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.

Анализ алгоритма

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим -- массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных

Сортировка выбором

Алгоритм может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае И(n2), предполагая что сравнения делаются за постоянное время.

Алгоритм

Шаги алгоритма:

1.находим минимальное значение в текущем списке

2.производим обмен этого значения со значением на первой неотсортированной позиции

3.теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

Анализ сортировки

К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). В лучшем случае (когда исходный

массив уже упорядочен) потребуется поменять местами только n-1элементов,а каждая операция обмена требует три операции пересылки.

Пирамидальная сортировка

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») -- алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за И(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Идея алгоритма

Пирамида -- двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.

Заполнив дерево элементами в произвольном порядке, можно легко его отсортировать (легче, чем исходный список элементов), превратив в пирамиду.

Самый большой элемент пирамиды находится в её вершине.

Отделяем вершинный элемент, и записываем его в конец результирующего массива.

На место вершинного элемента записываем элемент из самого нижнего уровня дерева.

Восстанавливаем (пересортировываем) пирамиду.

Самый большой элемент из оставшихся снова в вершине. Снова отделяем его и записываем его в качестве предпоследнего элемента результата, и так далее...

Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исход­ном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается начиная с конца массива на освободив­шиеся от пирамиды места.

Достоинства и недостатки

Достоинства

1.Имеет доказанную оценку худшего случая .

2.Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

1.Сложен в реализации.

2.Неустойчив -- для обеспечения устойчивости нужно расширять ключ.

3.На почти отсортированных массивах работает столь же долго, как и на хаотических данных.

4.На одном шаге выборку приходится делать хаотично по всей длине массива -- поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Технологический раздел

Блок-схема программы

В курсовой работе использовались следующие стандартные заголовочные файлы:

<iostream.h> -- заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++. Он включён в стандартную библиотеку C++. Название образовано от Input/Output Stream («поток ввода-вывода»). В языке C++ и его предшественнике, языке программирования Си, нет встроенной поддержки ввода-вывода, вместо этого используется библиотека функций. iostream управляет вводом-выводом, как и stdio.h в Cи. iostream использует объекты cin, cout, cerr и clog для передачи информации в и из стандартных потоков ввода, вывода, ошибок (без буферизации) и ошибок (с буферизацией) соответственно. Являясь частью стандартной библиотеки C++, эти объекты также являются частью стандартного пространства имён -- std.

<stdlib.h> -- заголовочный файл стандартной библиотеки языка Си, который содержит в себе функции, занимающиеся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие. Заголовок вполне совместим с C++ и известен в нём как cstdlib. Название «stdlib» расшифровывается как «standard library» (стандартная библиотека).

<stdio.h> (от англ. standard input/output header -- стандартный заголовочный файл ввода/вывода) заголовочный файл стандартной библиотеки языка Си, содержащий определения макросов, константы и объявления функций и типов, используемых для различных операций стандартного ввода и вывода. Функциональность унаследована от «портативного пакета ввода/вывода» («portable I/O package»), написанного Майком Леском из Bell Labs в начале 1970-х. C++ ради совместимости, также использует stdio.h наряду со схожим по функциональности заголовочным файлом cstdio.

<conio.h> (от англ. console input-output -- консольный ввод-вывод) -- заголовочный файл, используемый в старых компиляторах, работающих в операционных системах MS-DOS.Этот заголовочный файл объявляет несколько библиотечных функций для работы с «консольным вводом и выводом» программы

<string.h> -- заголовочный файл стандартной библиотеки языка Си, содержащий функции для работы с нуль-терминированными строками и различными функциями работы с памятью.Функции объявленные в string.h широко используются, так как являясь частью стандартной библиотеки, они гарантированно работают на всех платформах, поддерживающих Си. Кроме этого, строковые функции работают только с набором символов ASCII или его совместимыми расширениями, такими как ISO-8859-1; многобайтовые кодировки такие как UTF-8 будут работать, с отличием, что «длина» строки будет определяться как число байтов, а не число символов Юникода, которым они соответствуют

< graphics.h > - стандартная библиотека С++ подключающая графический режим.

Стандартные типы данных:

В данной программе используются следующие стандартные переменные:

Ш int целочисленный знаковый тип данных, диапозон от -32768…32767. Размер 1 байт

Ш long int целочисленный знаковый тип данных,диапозон от 2147483648…2147468647.Размер 4 байта.

Ш char символьный тип данных, предназначенный для хранения одного символа в определённой кодировке. Если char определён как signed (знаковый), то его диапазон значений составляет от ?127 до 127 (на единицу больше в положительную или отрицательную сторону, в зависимости от реализации). Если он определён как unsigned (беззнаковый), то его значения могут составлять от 0 до 255. Значение, содержащееся в этом типе, можно всегда безопасно привести к значению типа int. В Си нет примитивных типов для работы со строками, поэтому для работы с ними используется указатель char *.

Ш double вещественный тип данных с плавающей точкой и двойной точностью.Диапозон 1,7е-308…1,7е+308.Размер 8 байт.

struct time t;

gettime(&t);

printf(“Еру current time is: %2d:%02d:%02d:%02d\n”, t.ti_hour, t.ti_min, t.ti_sec , t.ti_hund, )

Данная структура выводит время в которое была вызвана данная функция.

t.ti_hour - поле структуры выводящее часы.

t.ti_min - поле структуры выводящее минуты.

t.ti_sec - поле структуры выводящее секунды.

t.ti_hund - поле структуры выводящее миллисекунды.

Описание собственных функций,которые используются в программе

“SORTI.CPP”-модуль,в котором находятся подпрограммы 4-х сортировок, подпрограммы выводящие время начала сортировки и время конца сортировки и общее время сортировки,подпрограмма генерирование массива(случайным образом,по убыванию и по возрастанию)

“FILI.CPP”- модуль в котором находятся подпрограммы записи данных на внешнюю память.

void puzir(int*& kop,int razmer) - даннай функций сортирует переданный массив методом пузырька.

Пример работы алгоритма:

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах

(8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)Теперь массив отсортирован и алгоритм может быть завершён.

void protalkivanie(int*& kop,int razmer) - функция сортирующая массив методом выбора.

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

void vstavka(int*& kop,int razmer) - функция сортирующая массив методом вставки.

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность.

Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы.

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.

Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.

В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.

Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда

1.Hайден элемент, меньший x или

2.Достигнуто начало последовательности.

void Pirmidalina9(kop,razmer,iter) - функция сортирующая массив пирамидальной сортировкой.

Пошаговое описание алгоритма

1. Построение пирамиды

Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим потомкам (таким образом, на вершине дерева всегда находится наибольший элемент).

Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).

Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры - это индексы элементов массива, а ни в коем случае не значения этих элементов):

Таким образом, для того, чтобы

каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].

2. Сортировка

В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т.е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.

На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.

int Zadaniemassiva(int midx,int midy,int& metod,long int& razmer,int& p) - функция в которой задаётся размер массива,метод заполнения массива(рандомом,по возрастанию и по убыванию).Максимально вводимое число массива 24500 элементов.Пока не будет задан массив в программе будет активно только 2 кнопки “Задание массива” и “Exit”.

int F1(int midx,int midy) { - функция прорисовывающая название кнопок.

moveto((midx-7*14),midy-30);

outtext("Zadanie parametrov masiva");

moveto((midx-7*3),midy);

outtext("Puzirek");

moveto((midx-7*3),midy+30);

outtext("Vstavki");

moveto((midx-7*7),midy+60);

outtext("Protalkivani9");

moveto((midx-7*7),midy+90);

outtext("Piramidalina9");

moveto((midx-7*2),midy+120);

outtext("Exit");

return 0;

}

int F(int midx,int midy,int h,int p) { - функция прорисовывающая кнопки меню.

int y=midy;

for (int i=-30;i<=120;i+=30) {

if (p==0) { //если переменная р=0 то это значит что массив ещё не задан и активнми будут только кнопки “Задание массива” и ”Exit”.

setfillstyle(1,7);

bar(midx-100, y-10+i, midx+100,y+10+i);

}

if ((p==1) || (-1==(i/30)) || ((i/30)==4)) { // p=1 массив задан все кнопки меню активны.

setfillstyle(1,2);

bar(midx-100, y-10+i, midx+100,y+10+i);

}

if (h==(i/30)) { //данное условие определяет какая кнопка сейчас активна.

setfillstyle(1,3);

bar(midx-100, y-10+i, midx+100,(y+10)+i);

}

}

return F1(midx,midy);

}

int File(int*& kop,int k,int razmer) { - данная функция записывает отсортированный массив в файл с расширением .txt по убыванию или по возрастанию в зависимости от того,что выбрал пользователь.

FILE *out;

if ((out = fopen("c:\\BORLANDC\\BIN\\1.txt", "w")) == NULL) {

fprintf(stderr, "Cannot open output file.\n");

return 1; }

if (k==1) {

for (int i=0; i<razmer; i++) {

fprintf(out, "%d ", kop[i] );

}

}

if (k==0) {

for (int i=razmer-1; i>=0; i--) {

fprintf(out, "%d ", kop[i] );

}

}

fclose(out);

return 0;

}

Заключение

Были исследованы некоторые методы сортировок.Была изучена литература по алгоритмам сортировок,составлены подпрограммы сортировок,проведён анализ и вычислено среднее время каждой сортировки,а также составлено графическое меню для пользователей.

Анализ показал,что при исходном массиве заполненном рандомом лучшее время показывает пирамидальная сортировка,с относительно небольшим количеством итераций.При исходном массиве заполненном по возрастанию лучшее время показывает метод пузырька 0 секунд и колличетсво иттераций 0.При массиве сгенерированном по убыванию лучшее время показала пирамидальная сортировка.Ниже представлены средние результаты проведённого анализа при количестве 24500 элементов.

Метод сортировки	Среднее время (сек)	Кол.иттераций	тип заполнения массива
Пузырёк	1,37	150305841	Рандом
	0	0	По возрастанию
	2,58	300000000	По убыванию
Вставка	0,75	205291	Рандом
	0,33	0	По возрастанию
	1,26	150062500	По убыванию
Выбором	3,95	150000000	Рандом
	1,81	0	По возрастанию
	3,74	300000000	По убыванию
Пирамидальная	0,3	353265	Рандом
	0,1	353265	По возрастанию
	0,1	353118	По убыванию

Список литературы

1. http://ru.wikipedia.org/wiki/Сортировка_пузырьком

2. http://algolist.manual.ru/sort/select_sort.php

3. Русскоязычный форум по C++

4. Программирование на языке высокого уровня СИ. Часть II: практикум/Сост. О.В. Шестопал, О.В. Сташкова. - Тирасполь, 2010. - 83 с.

Приложение

Листинг программы

Файл МENU.CPP

#include <graphics.h>

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#include "SORTI.CPP"

#include "FILE.CPP"

int Zadaniemassiva(int midx,int midy,int& metod,long int& razmer,int& p) {

int i=0;

setfillstyle(0,1);

bar(0,0,midx*2,midy/2+40);

outtextxy(midx/25, midy/5, "Vvedite razmer massiva: ");

outtextxy(midx/25, midy/5-20, "Massiv ne bolee 24500 elementov!");

char symbol[6],m[2]={' ','\0'};

while ((i<5) && ((symbol[i]!=13) || (i==0))) {

symbol[i]=getch();

if ((symbol[0]!='0') && (symbol[i]>='0') && (symbol[i]<='9')) {

m[0]=symbol[i];

i++;

outtextxy(midx/25+190+i*8, midy/5, m);

}

else if ((symbol[i]==8) && (i!=0)){

setfillstyle(0,2);

bar(midx/25+190+i*8,midy/5+10,midx/25+190+i*12+50,midy/5-10);

i--;

}

}

symbol[i]='\0';

if (atol(symbol)>24500) return Zadaniemassiva(midx,midy,metod,razmer,p);

razmer=atoi(symbol);

setfillstyle(1,2);

bar(midx/25+26*7,midy/5+15,midx/25+26*7+16*7,midy/5+30);

outtextxy(midx/25, midy/5+20, "Tip zapolneni9 massiva: Random Po Vozrastaniu Po ubivaniju");

int x;

metod=1;

while (x!=13) {

x=getch();

if (x==77) {

setfillstyle(0,1);

bar(midx/25+26*7,midy/5+15,midx/25+1000,midy/5+30);

if (metod==3) metod=0;

metod++;

setfillstyle(1,2);

bar(midx/25+26*7+(metod-1)*16*7,midy/5+15,midx/25+26*7+metod*16*7,midy/5+30);

outtextxy(midx/25, midy/5+20, "Tip zapolneni9 massiva: Random Po Vozrastaniu Po ubivaniju");

if (metod==3) metod=0;

}

if (x==75) {

setfillstyle(0,1);

bar(midx/25+26*7,midy/5+15,midx/25+1000,midy/5+30);

if (metod==0) metod=3;

metod--;

if (metod==0) metod=3;

setfillstyle(1,2);

bar(midx/25+26*7+(metod-1)*16*7,midy/5+15,midx/25+26*7+metod*16*7,midy/5+30);

outtextxy(midx/25, midy/5+20, "Tip zapolneni9 massiva: Random Po Vozrastaniu Po ubivaniju");

}

}

p=1;

return 0;

}

int Podmenu(int midx,int midy,int h) {

moveto((midx+110),midy+h*30);

outtext("Po Ubivaniju");

moveto((midx+110),midy+h*30+30);

outtext("Po Vozrastaniju");

return 0;

}

int F1(int midx,int midy) {

moveto((midx-7*14),midy-30);

outtext("Zadanie parametrov masiva");

moveto((midx-7*3),midy);

outtext("Puzirek");

moveto((midx-7*3),midy+30);

outtext("Vstavki");

moveto((midx-7*7),midy+60);

outtext("Protalkivani9");

moveto((midx-7*7),midy+90);

outtext("Piramidalina9");

moveto((midx-7*2),midy+120);

outtext("Exit");

return 0;

}

int F(int midx,int midy,int h,int p) {

int y=midy;

for (int i=-30;i<=120;i+=30) {

if (p==0) {

setfillstyle(1,7);

bar(midx-100, y-10+i, midx+100,y+10+i);

}

if ((p==1) || (-1==(i/30)) || ((i/30)==4)) {

setfillstyle(1,2);

bar(midx-100, y-10+i, midx+100,y+10+i);

}

if (h==(i/30)) {

setfillstyle(1,3);

bar(midx-100, y-10+i, midx+100,(y+10)+i);

}

}

return F1(midx,midy);

}

int F2(int midx,int midy,int h,int k) {

int poly[12];

for (int i=0;i<60;i+=30) {

setfillstyle(1,2);

poly[0]= midx+100;

poly[1]= midy+h*30+i;

poly[2]=midx+110;

poly[3]=midy+10+h*30+i;

poly[4]=midx+230;

poly[5]=midy+10+h*30+i;

poly[6]=midx+230;

poly[7]=midy-10+h*30+i;

poly[8]=midx+110;

poly[9]=midy-10+h*30+i;

poly[10]=midx+100;

poly[11]=midy+h*30+i;

drawpoly(6, poly);

floodfill(midx+101,midy+h*30+i, 15);

if (k==(i/30)) {

setfillstyle(1,3);

poly[0]= midx+100;

poly[1]= midy+h*30+i;

poly[2]=midx+110;

poly[3]=midy+10+h*30+i;

poly[4]=midx+230;

poly[5]=midy+10+h*30+i;

poly[6]=midx+230;

poly[7]=midy-10+h*30+i;

poly[8]=midx+110;

poly[9]=midy-10+h*30+i;

poly[10]=midx+100;

poly[11]=midy+h*30+i;

drawpoly(6, poly);

floodfill(midx+101,midy+h*30+i, 15);

}

}

Podmenu(midx,midy,h);

return 0;

}

int main(void)

{

int gdriver = DETECT, gmode, errorcode;

int midx, midy, i;

initgraph(&gdriver, &gmode, "");

midx = getmaxx() / 2;

midy = getmaxy() / 3;

int j=midy-30;

int h=-1,k=0,p=0;

unsigned long int iter=0;

char x;

char* s;

char* d;

int metod,r;

long int razmer;

double time1,s1;

while (x!=113) {

F(midx,midy,h,p);

x=getch();

if (x==80) {

h++;

setfillstyle(0,2);

bar(0,midy/2,midx/2+60,midy*2);

bar(0,midy/2,midx*2,midy/2+40);

bar(midx/25,midy+170,midx,midy+190);

}

if (x==72) {

h--;

setfillstyle(0,2);

bar(0,midy/2,midx/2+60,midy*2);

bar(0,midy/2,midx*2,midy/2+40);

bar(midx/25,midy+170,midx,midy+190);

}

if (h==5) h=-1;

if (h==-2)h=4;

if (p==0) {

if (h==0) h=4;

if (h==3) h=-1;

}

F(midx,midy,h,p);

if ((x==13) && (h!=4) && (h!=-1)) { int k=0;

setfillstyle(0,2);

bar(0,midy/2+20,midx/2+60,midy*2);

bar(0,midy/2,midx*2,midy/2+40);

bar(midx/25,midy+170,midx,midy+190);

while (x!=8) {

if (x==80) k++;

if (x==72) k--;

if (k==2) k=0;

if (k==-1) k=1;

F2(midx,midy,h,k);

x=getch();

if (x==13) {

int* kop=new int[razmer];

massiv(kop,razmer,metod);

moveto(midx/25,midy/2);

outtext("Massiv sgenerirovan");

moveto(midx/25,midy/2+20);

outtext("i soxranen v");

moveto(midx/25,midy/2+40);

outtext("C:/BORLANDC/BIN/2.BAK");

File1(kop,razmer);

if (h==0){

na4alo(time1,r,s1);

puzir(kop,razmer,iter);

konec(time1,r,s1);

}

if (h==1) {

na4alo(time1,r,s1);

vstavka(kop,razmer,iter);

konec(time1,r,s1);

}

if (h==2) {

na4alo(time1,r,s1);

protalkivanie(kop,razmer,iter);

konec(time1,r,s1);

}

if (h==3) {

na4alo(time1,r,s1);

Pirmidalina9(kop,razmer,iter);

konec(time1,r,s1);

}

File(kop,k,razmer);

x=8;

delete (kop);

moveto(midx/25,midy);

outtext("Massiv otsortirovan");

if (h==0) {

moveto(midx/25,midy+20);

outtext("metodom puzirika!");

}

if (h==1) {

moveto(midx/25,midy+20);

outtext("Metodom vstavki!");

}

if (h==2) {

moveto(midx/25,midy+20);

outtext("Metodom protalkivani9!");

}

if (h==3) {

moveto(midx/25,midy+20);

outtext("Piramidalinoi sortirovkoi");

}

moveto(midx/25,midy+40);

outtext("Massiv soxranen v");

moveto(midx/25,midy+60);

outtext("C:/BORLANDC/BIN/1.BAK");

ultoa(iter,d,10);

outtextxy(midx/25,midy+180,"Kolli4estvo itteracii:");

outtextxy(midx/25+7*25,midy+180,d);

}

}

setfillstyle(1,16);

bar (midx+100,midy-90,midx+300,midy+200);

}

if ((x==13) && (h==4)) x=113;

if ((x==13) && (h==-1)) Zadaniemassiva(midx,midy,metod,razmer,p);

}

closegraph();

return 0;

}

Файл SORTI.CPP

#include <dos.h>

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

int na4alo(double& time1,int& r,double& s1) {

char min[10];

char sec[10];

char chas[10];

char hund[10];

struct time t;

gettime(&t);

itoa(t.ti_hour,chas,10);

itoa(t.ti_min,min,10);

itoa(t.ti_sec,sec,10);

itoa(t.ti_hund,hund,10);

for (int i=0;min[i];i++);

if (i==1) {

min[1]=min[0];

min[0]='0';

sec[2]='\0';

}

for (i=0;sec[i];i++);

if (i==1) {

sec[1]=sec[0];

sec[0]='0';

sec[2]='\0';

}

for (i=0;hund[i];i++);

if (i==1) {

hund[1]=hund[0];

hund[0]='0';

hund[2]='\0';

}

setfillstyle(1,0);

bar(300,390,300+40*7,450);

outtextxy(300,400,"Vremia na4ala sortirovki:");

outtextxy(300+29*7,400,chas);

outtextxy(300+31*7,400,":");

outtextxy(300+32*7,400,min);

outtextxy(300+34*7,400,":");

outtextxy(300+35*7,400,sec);

outtextxy(300+37*7,400,".");

outtextxy(300+38*7,400,hund);

s1=t.ti_hund;

time1=t.ti_min*60+t.ti_sec+(s1/100);

r=t.ti_hour;

return 0;

}

void konec(double time1,int r,int s1)

{

int r2;

char min[10];

char sec[10];

char chas[10];

char hund[10];

char time[10];

char timer[10];

struct time t2;

gettime(&t2);

itoa(t2.ti_hour,chas,10);

itoa(t2.ti_min,min,10);

itoa(t2.ti_sec,sec,10);

itoa(t2.ti_hund,hund,10);

for (int i=0;min[i];i++);

if (i==1) {

min[1]=min[0];

min[0]='0';

sec[2]='\0';

}

for (i=0;sec[i];i++);

if (i==1) {

sec[1]=sec[0];

sec[0]='0';

sec[2]='\0';

}

for (i=0;hund[i];i++);

if (i==1) {

hund[1]=hund[0];

hund[0]='0';

hund[2]='\0';

}

setfillstyle(1,0);

bar(300+29*7,410,300+40*7,430);

outtextxy(300,420,"Vremia konca sortirovki:");

outtextxy(300+29*7,420,chas);

outtextxy(300+31*7,420,":");

outtextxy(300+32*7,420,min);

outtextxy(300+34*7,420,":");

outtextxy(300+35*7,420,sec);

outtextxy(300+37*7,420,".");

outtextxy(300+38*7,420,hund);

double s2=t2.ti_hund;

r2=t2.ti_hour;

r2=r2-r;

double time2=r2*3600+t2.ti_min*60+t2.ti_sec+(s2/100);

time2=time2-time1;

itoa(time2,time,10);

if (s1>s2) s2=100+s2-s1;

else s2=s2-s1;

itoa(s2,timer,10);

for(i=0;timer[i];i++);

if (i==1) {

timer[1]=timer[0];

timer[0]='0';

timer[2]='\0';

}

outtextxy(300,440,"Vremia sortirovki:");

outtextxy(300+21*7,440,time);

outtextxy(300+22*7,440,".");

outtextxy(300+23*7,440,timer);

}

void puzir(int*& kop,int razmer,unsigned long int& iter) {

int temp,a;

iter=0;

for(int i=1;i<razmer;i++) { a=i;

while ((a) && (kop[a]<kop[a-1])) {

temp=kop[a-1];

kop[a-1]=kop[a];

kop[a]=temp;

a--;

iter++;

}

}

}

void vstavka(int*& kop,int razmer,unsigned long int& iter) {

int min,index,temp;

iter=0;

for (int k=0;k<razmer;k++){ min=kop[k]; index=k;

for (int i=k;i<razmer;i++) {

if (min>kop[i]) {

min=kop[i];

index=i;

iter++;

}

}

temp=kop[k];

kop[k]=kop[index];

kop[index]=temp;

}

}

void protalkivanie(int*& kop,int razmer,unsigned long int& iter) {

int temp;

iter=0;

for (int k=0;k<razmer-1;k++) {

for (int i=0;i<razmer-1;i++) {

if (kop[i]>kop[i+1]) {

temp=kop[i];

kop[i]=kop[i+1];

kop[i+1]=temp;

iter++;

}

}

}

}

void Pirmidalina9(int*& kop,int razmer,unsigned long int& iter) {

int temp,b,z,g;

iter=0;

for (long int i=razmer-1;i>=0;i--) {

kop[i]=random(razmer);

}

for (z=0;z<razmer;z++) { b=1; i=z;

while ((b) && (i>0)) { iter++;

if ((i%2==0) && (kop[i]>kop[i/2-1])) {

temp=kop[i];

kop[i]=kop[i/2-1];

kop[i/2-1]=temp;

i=i/2-1;

}

else if ((i%2==1) && (kop[i]>kop[i/2])) {

temp=kop[i];

kop[i]=kop[i/2];

kop[i/2]=temp;

i=i/2;

}

else b=0;

}

}

g=razmer;

while (g>0) {

temp=kop[0];

kop[0]=kop[g-1];

kop[g-1]=temp;

g--;

i=0; b=1;

while ((b) && (i*2+1<g)) { iter++;

if ((kop[i]<kop[i*2+1]) && (kop[i]>=kop[i*2+2]) && (i*2+1<g)) {

temp=kop[i];

kop[i]=kop[i*2+1];

kop[i*2+1]=temp;

i=i*2+1;

}

else if ((kop[i]<kop[i*2+2]) && (kop[i]>=kop[i*2+1]) && (i*2+2<g)){

temp=kop[i];

kop[i]=kop[i*2+2];

kop[i*2+2]=temp;

i=i*2+2;

}

else if ((kop[i]<kop[i*2+1]) && (kop[i]<kop[i*2+2])) {

if ((kop[i*2+1]<kop[i*2+2]) && (i*2+2<g)) {

temp=kop[i];

kop[i]=kop[i*2+2];

kop[i*2+2]=temp;

i=i*2+2;

}

else {

temp=kop[i];

kop[i]=kop[i*2+1];

kop[i*2+1]=temp;

i=i*2+1;

}

}

else b=0;

}

}

}

int massiv(int*& kop,int razmer,int metod) {

if (metod==1) {

for (int i=0;i<razmer;i++)

kop[i]=random(razmer);

}

if (metod==2) {

for (int i=0;i<razmer;i++)

kop[i]=i;

}

if (metod==3) {

for (int i=razmer-1;i>=0;i--)

kop[i]=razmer-i-1;

}

return 0;

}

Файл FILE.CPP

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

int File(int*& kop,int k,int razmer) {

FILE *out;

if ((out = fopen("c:\\BORLANDC\\BIN\\1.txt", "w")) == NULL) {

fprintf(stderr, "Cannot open output file.\n");

return 1; }

if (k==1) {

for (int i=0; i<razmer; i++) {

fprintf(out, "%d ", kop[i] );

}

}

if (k==0) {

for (int i=razmer-1; i>=0; i--) {

fprintf(out, "%d ", kop[i] );

}

}

fclose(out);

return 0;

}

int File1(int*& kop,int razmer) {

FILE *out;

if ((out = fopen("c:\\BORLANDC\\BIN\\2.txt", "w")) == NULL) {

fprintf(stderr, "Cannot open output file.\n");

return 1; }

for (int i=0; i<razmer; i++) {

fprintf(out, "%d ", kop[i] );

}

fclose(out);

return 0;

}

Размещено на Allbest