Загрузка...
Учебная работа. Курсовая работа: Анализ методов сортировки одномерного массива
ХЕРСОНСКИЙ ГОСУДАРСТВЕННЫЙ технический УНИВЕРСИТЕТ
Кафедра ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
рАЗРАБОТКА ПРОГРАММЫ ДЛЯ
Анализа способов сортировки одномерных массивов.
Курсовой проект
по дисциплине «Программирование»
Объяснительная записка
Исполнитель
студент группы 2КСС3 ________________________
(подпись, дата)
Управляющий
старший педагог ________________________
(подпись, дата)
Нормоконтролер
старший преподаватель_________________________
(подпись, дата)
РЕФЕРАТ
Курсовой проект содержит: стр. – 39 машинописного текста, литературных источников – 5, приложения – 2 .
Главные слова: ФУНКЦИЯ, ФАЙЛ, МЕТОД , МАССИВ .
В курсовом проекте рассмотрена модификация и сопоставления 2-ух текстовых файлов. программка написана на языке программирования Cи и работоспособна на IBM совместимых компах. программка имеет псевдографический и графический интерфейсы, владеет достаточным быстродействием и маленьким размером.
СОДЕРЖАНИЕ
Введение ………………………………………………………………………………………. 3
1. Постановка задачки…………………………………………………………………….. 5
1.1. анализ имеющихся решений поставленной задачки……………. 5
1.2. Обоснование выбора способа решения задачки…………………………. 16
2. Разработка метода решения задачки……………………………………….. 17
3. Разработка программки……………………………………………………………… 18
3.1 Описание программки и применяемых в ней функций ………………. 18
3.1.1 Описание функции main()……………………………………………………… 21
3.1.2 Описание функции srecmg()…………………………………………………… 21
3.1.3 Описание функций qqsort()……………………………………………………. 22
3.1.4 Описание функции grafix()…………………………………………………….. 23
3.2 Управление программера …………………………………………………….. 25
3.3 Управление оператора ………………………………………………………….. 26
Заключение……………………………………………………………………………………. 28
Перечень использованной литературы……………………………………………….. 29
приложение 1 ………………………………………………………………………………. 30
Приложение 2 ………………………………………………………………………………. 39
ВВЕДЕНИЕ
Си – это язык программирования общего предназначения, отлично узнаваемый собственной эффективностью, экономичностью, и переносимостью. Обозначенные достоинства Си обеспечивают не плохое свойство разработки практически хоть какого вида программного продукта. Внедрение Си в качестве инструментального языка дозволяет получать довольно резвые и малогабаритные программки. В почти всех вариантах программки, написанные на Си, сравнимы по скорости с программками, написанными на языке ассемблера[2]. При всем этом они имеют наилучшую наглядность.
Си соединяет эффективность и мощность в относительно малом по размеру языке. Хотя Си не содержит интегрированных компонент языка, выполняющих ввод-вывод, распределение памяти, манипуляций с экраном либо управление действиями, тем не наименее, системное свита Си располагает библиотекой объектных модулей[3], в какой реализованы подобные функции. библиотека[4] поддерживает почти все из функций, которые требуются.[1]
язык Си – это всепригодный язык программирования, для которого свойственны экономичность выражения, современный поток управления и структуры данных, обеспеченный набор операторов. язык Си не является ни языком «весьма высочайшего уровня», ни «огромным» языком, и не предназначается для некой специальной области внедрения, но отсутствие ограничений и общность языка делают его наиболее комфортным и действенным для почти всех задач, чем языки, предположительно наиболее массивные.
Он тесновато связан с операционной системой «unix«[4] , потому что был развит на данной нам системе и потому что «unix» и ее программное обеспечение написано на «C». Сам язык, но, не связан с какой–или одной операционной системой либо машинкой; и хотя его именуют языком системного программирования, потому что он комфортен для написания операционных систем, он с равным фуррором употреблялся при написании огромных вычислительных программ, программ для обработки текстов и баз данных [2].
2. ПОСТАНОВКА задачки
2.1 анализ СУЩЕСТВУЮЩИХ РЕШЕНИЙ ПОСТАВЛЕННОЙ ЗАДАЧИ
В истинное время существует огромное количество алгоритмов cортировки[5] массивов, которые используются зависимо от того какие условия функционирования стоят перед разрабатымаемой программкой.
1. способы вставки. метод обычных вставок.
1.1. Бинарные вставки
1.2. Двухпутевые вставки
1.3. Вставки сразу нескольких частей.
1.4. Вставки с убывающим шагом (способ Шелла)
1.5. Вставки в связанный перечень
1.6. Вставки в несколько связанных списков
2. Обменная сортировка
2.1. Способ пузырька
2.2. Модификация способа пузырька
2.3. Стремительная сортировка.
2.4. Обменная поразрядная сортировка
2.5. Параллельная сортировка Бэтчера
3. Сортировка средством выбора
( Внедрение связанного перечня для хранения
инфы о промежных максимумах.)
4. Сортировка средством слияния
способы вставки. метод обычных вставок.
Ниже описан главный метод обычных вставок, который порождает несколько модификаций, применяемых в заданиях. метод употребляет прием, которым пользуются игроки в карты при сортировке лишь что розданной колоды: еще одна карта вставляется меж уже упорядоченными ранее.
Описание метода обычных вставок. файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым делается упорядочение по возрастанию. Так как информационная часть практически не влияет на процесс сорировки, будем полагать, что файлы, применяемые в примерах, состот лишь из элементов-ключей, а информационная часть записи от сутствует.
Время работы метода t приблизительно оценивается формулой:
t=a*NЅ+ b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Бинарные вставки
Для убыстрения числа сравнений при поиске места, в которое необходимо вставить элемент X, можно применять логарифмический [5] поиск. Это значит, что поначалу Х сравнивается с элементом k[j/2], потом, зависимо от результата сопоставления, с элементом, лежащим в центре меж 1 и j/2 либо в центре меж j/2+1 и j и т.д. . При всем этом числосравнений для всякого j равно приблизительно log(j). Число пересылок эле ментов при всем этом не меняется и остается приблизительно равным NЅ/4.
время работы метода t приблизительно оценивается формулой:
t=a*NЅ + b*N + c*N*logN
где a,b,c — неведомые константы, зависящие от программной реализации метода.
Двухпутевые вставки
Число пересылок можно уменьшить приблизительно в 2 раза до NЅ/8, если допустить сдвиги частей не только лишь на Право, да и на лево. Для выходного файла резервируется пространство в памяти, равное 2N+1 ,где N — число частей в начальном файле. 1-ый элемент пересылается в середину выходного файла. В предстоящем элементы выходного файла сдвигаются на Право либо на лево зависимо от того, в какую сторону необходимо сдвигать меньше частей. Присоединение новейших частей к выходному файлу происходит как справа, так и слева от центрального элемента с вероятным сдвигом на Право либо на лево.
время работы метода t приблизительно оценивается формулой:
t=a*NЅ + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Вставки сразу нескольких частей.
Модификация способа обычных вставок состоит в том, что заместо одной переменной Х можно применять несколько переменных Х1, Х2, … Xm, которые имеют значения частей, подлежащих вставке в уже упорядоченную часть файла. Х1, X2, … Xm упорядочены по возрастанию, потому сравнивая Xm в цикле по переменной i с элементами упорядоченной части, мы можем гарантировать, что, если очередной элемент k[i] больше Xm, то он больше и других частей. Перенос частей начального файла вперед в цикле по i производится на m частей, другими словами заместо k[i+1]=k[i] в начальном методе в измененном методе записывается k[i+m]=k[i]. При нахождении k[i] такового, что он меньше Хm, Хm ставится на пространство k[i+m] и m миниатюризируется на 1. Дальше цикл по i продол-жается с новеньким m. Экономия числа переносов частей получается из-за переносов сходу на m частей.
время работы метода t приблизительно оценивается формулой:
t=a*NЅ + b*N + c*N*logN
где a,b,c — неведомые константы, зависящие от программной реализации метода.
Вставки с убывающим шагом (способ Шелла)
Мысль метода состоит в обмене частей, расположенных не только лишь , как в методе обычных вставок (п.1), да и далековато друг от друга, что существенно уменьшает общее число операций перемещения частей. Для примера возьмем файл из 16 частей. Поначалу просматриваются пары с шагом 8. Это пары частей 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения частей в паре не упорядочены по возрастанию, то элементы изменяются местами. Назовем этот шаг 8-сортировкой. Последующий шаг — 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15,4-8-12-16. Производится сортировка в каждой четверке. Сортировка может производиться способом обычных вставок (п.1). Последующий шаг — 2-сортировка, когда элементы в файле делятся на 2 группы по 8:
1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Производится сортировка в каждой восьмерке. В конце концов весь файл упорядочивается способом обычных вставок. Так как далекие элементы уже переместились на свое пространство либо находятся поблизости от него, этот шаг будет существенно наименее трудозатратным, чем при сор-тировке вставками без подготовительных «далеких» обменов.
файл опосля конечной сортировки (1-сортировки): 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908
время работы метода t приблизительно оценивается формулой: t=a*N**b
где a и b — неведомые константы, зависящие от программной реализа-
ции метода.
Вставки в связанный перечень
Посреди общих методов улучшения метода обычных вставок можно разглядеть метод, основанный на изменении структуры данных. Сортировка ординарными вставками состоит из 2-ух главных операций:
— просмотра начального файла со сопоставлением переменной Х с
элементами K[i] файла;
— вставки новейшего элемента методом сдвига оставшихся частей
на Право.
файл до сего времени рассматривался как линейный перечень и для выполнения операции вставки в нем нужно переместить в среднем половину эле-ментов . Понятно, что для операций вставки совершенно подходитсвязанный перечень, потому что в этом случае вставка просит всего только конфигурации нескольких связей. Операция поочередного просмотра для связанного перечня практически так же ординарна, как и для линейного перечня. Так как файл постоянно просматривается в одном направлении, то довольно иметь перечень лишь с одной связью. С иной стороны связанное распределение делает неосуществимым бинарный поиск, потому приобретая преимущество в выполнении операции вставки, мы теряем по сопоставлению с бинарным поиском в эффективности операции просмотра и сопоставления. Разглядим метод обычных вставок на связанном вперед перечне.
Дан файл в виде связанныого перечня, любой элемент которого содержит не считая ключа K[i] к тому же указатель на последующий элемент L[i].
Не считая того еще есть доборная переменная L[0], содержащая указатель на крайний N-й элемент файла. Указатель L[N] равен нулю, что является признаком конца перечня частей.
время работы метода t приблизительно оценивается формулой: t=a*NЅ + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Вставки в несколько связанных списков
Мысль способа основывается на предположении, что ключи в начальном файле имеют значения в неком известном спектре MAX и в этом спектре они распределены достаточно умеренно. Тогда по аналогии с способом вставки в один связанный перечень можно организовать несколько, к примеру, Q списков. Величина Q зависит от ожидаемого среднего количес-тва частей M в любом перечне другими словами Q=N/M, N — количество ключей.
При разработке программки необходимо проанализировать зависимость времени работы способа от параметра М для разных начальных файлов и отдать советы по выбору рационального значения.
Схема метода имеет последующий вид. Через Q обозначено количество списков, массив B[1]…B[Q] служит для хранения указателей на начала отдельных списков. Перед началом работы метода элементы массива В предполагаются равными 0. Любой i-й элемент начального файла содержит ключ K[i] и указатель L[i] на последующий элемент перечня. должен быть вставлен элемент K[j]. Величина R=MAX/Q есть спектр значений ключей, приходящийся на один перечень.
Время работы метода t приблизительно оценивается формулой: t=a*NЅ + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Обменная сортировка
Заглавие данной нам группы способов вышло от основного типа операций, применяемого в методах — обмен 2-ух частей в файле своими значениями. Эта операция употребляется и в остальных группах, потому систематизацию недозволено признать полностью серьезной, но данное разделение тем не наименее является обычным. файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым делается упорядочение по возрастанию.
Так как информационная часть практически не влияет на процесс сортировки, будем полагать, что файлы, применяемые в примерах, состот лишь из элементов-ключей, а информационная часть записи отсутствует.
Способ пузырька
Метод достаточно очевиден.
Пары стоящих частей просматриваются в направлении снизу ввысь и сравниваются. Если верхний элемент оказывается меньше нижнего, то они изменяются местами. Продолжая этот процесс циклически, мы в конце концов придем к отсортированному файлу.файл размещен вертикально снизу ввысь, чтоб эффект всплывающего пузырька смотрелся наиболее наглядно. Элементы с огромным значением ключа «всплывают» наверх, опосля поочередных сравнивнений с примыкающими элементами.
время работы метода t приблизительно оценивается формулой: t=a*NЅ + b*N
где a,b — неведомые константы, зависящие от программной реализа-
ции метода.
Модификация способа пузырька
Модификация способа пузырька заключается в том, что файл можно просматривать как с начала до конца, так и с конца до начала попеременно. Это несколько уменьшает число перемещений частей.
Время работы метода t приблизительно оценивается формулой: t=a*NЅ + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Стремительная сортировка.
Основная стратегия убыстрения алгоритмов сортировка — обмены меж как можно наиболее далекими элементами начального файла — в способе резвой сортировки реализована за счет того, что один из ключей в начальном файле употребляется для разделения его на два подфайла так, чтоб слева от избранного элемента находились лишь элементы с наименьшими ключами,а справа — лишь с большенными. Элемент, разделяющий файл, помещается меж его 2-мя подфайлами и процедура производится рекурсивно для каждой половины до того времени, пока в следующем новеньком подфайле не окажется меньше, чем М частей, где М — заблаговременно выбранное число.
Сортировка подфайлов, содержащих меньше чем М частей, производится любым обычным способом, к примеру ординарными вставками. Таковым образом, реализация способа зависит от 2-ух характеристик: значения М и метода выбора элемента, который предназначен для разделения файла на две части.
Блок выбора Х в простом случае формулируется как X=K[l], но это может привести к очень неэффективному методу. Более обычное наилучшее решение — выбирать Х как случайный ключ из спектра K[l] … K[r] и поменять его с K[l].
время работы метода t приблизительно оценивается формулой:
t=a*N*logN + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Обменная поразрядная сортировка
Данный способ употребляет двоичное
время работы метода t приблизительно оценивается формулой:t=a*N*logN + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Параллельная сортировка Бэтчера
Для получения метода обменной сортировки, время работы которого меньше, чем NЅ, нужно выбирать для сопоставления и обмена ключи,расположенные может быть далее друг от друга. Эта мысль уже была реализована в методе сортировки Шелла вставок с убывающим шагом, но в данном методе сопоставления производятся по-другому.
время работы метода t приблизительно оценивается формулой:t=a*N*(logN)Ѕ
где a,b — неведомые константы, зависящие от программной реализации метода.
Сортировка средством выбора
Мысль способа достаточно ординарна: отыскать больший элемент файла и по-ставить его на пространство N, отыскать последующий максимум и поставить его на пространство N-1 и т.д. до 2-го элемента.
время работы метода t приблизительно оценивается формулой: t=a*NЅ+b*N* logN
где a,b — неведомые константы, зависящие от программной реализации метода.
Внедрение связанного перечня для хранения инфы о проме-жуточных максимумах.
В методе максимум посреди K[1] … K[j-1] определяется в цикле от j-1 до 1 c целью обеспечить наименьшее число обменов в случае равенства ключей и сохранении прежнего порядка равных частей. Но, если поменять порядок просмотра частей на обратный и поменять структуру данных, введя доп указатели, можно пример-но вдвое уменьшить число повторений в цикле поиска максисмума. Любой ключ K[i] снабжается указателем L[i] на элемент, наибольший посреди первых i-1 частей .
Тогда опосля обмена частей K[j] и K[m] поиск максимума в последующем цикле по j можно производить посреди частей K[L[m]] … K[j] при началь-ных значениях X=K[L[m]], m=L[m], т.к. максимум может «обновиться» лишь за счет частей, лежащих правее локального максимума. Таковым образом среднее количество просматриваемых при поиске максимума частей со-кращается приблизительно вдвое.
время работы метода t приблизительно оценивается формулой:t=a*NЅ + b*N*logN
где a,b — неведомые константы, зависящие от программной реализации метода.
Сортировка средством слияния
методы сортировки этого класса основываются на объединении нескольких (нередко 2-ух) уже упорядоченнх файлов. Рассмотренные дальше методы выбирают из начального файла упорядоченные отрезки и объединяют их в наиболее длинноватые.
Естественное двухпутевое слияние
Этот метод отыскивает упорядоченные отрезки с 2-ух концов файла ипереписывает их по очереди также в оба конца. Повторяя эту функцию в цикле, мы приходим к середине файла, что значит окончание сортировки.
Элементы файла пересылаются из одной области в другую, меняя направление пересылки. Для запоминания направления пересылки служит переменная s, принимающая значения TRUE и FALSE попеременно. Иной логический признак f служит сигналом продолжения-окончания метода, если все области соединились в конце концов в одну. Переменная d воспринимает попеременно значения +1 -1 и показывает направление просмотра файла: вперед либо вспять.Операция <-> обозначает обмен значениями 2-ух переменных. Операция Џ обозначает инверсию логической переменной либо выражения.
время работы метода t приблизительно оценивается формулой:
t=a*N*lgN + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
Обычное двухпутевое слияние.
В методе естественного двухпутевого слияния упорядоченный отрезки файла определялись случайным расположением частей в начальном файле. В данном методе длина отрезков фиксируется на любом шаге. В начальной файле все отрезки имеют длину 1, опосля первого шага она равна 2, опосля второго 4, опосля третьего — 8, опосля к-го шага -2 в степени к.
время работы метода t приблизительно оценивается формулой: t=a*N*lgN + b*N
где a,b — неведомые константы, зависящие от программной реализации метода.
1.2 ОБОСНОВАНИЕ ВЫБОРА МЕТОДА РЕШЕНИЯ задачки
Сортировка массива резвым способом является красивым примером целесооразности использования рекурсивного воззвания в программированние на языке Си . способ резвой сортировки был предложен К. А. Р. Хоором в 1962г. Предложенная версия резвой сортировки , очевидно , не самая стремительная посреди всех вероятных ,но зато она из самых обычных .
Основная стратегия убыстрения алгоритмов сортировки — обмены меж как можно наиболее далекими элементами начального файла — в способе резвой сортировки реализована за счет того, что один из ключей в начальном файле употребляется для разделения его на два подфайла так, чтоб слева от избранного элемента находились лишь элементы с наименьшими ключами,а справа — лишь с большенными.
методы сортировки способом слияния основываются на объединении нескольких (нередко 2-ух) уже упорядоченнх файлов. Этот метод отыскивает упорядоченные отрезки с 2-ух концов файла и переписывает их по очереди также в оба конца. Повторяя эту функцию в цикле, мы приходим к середине файла, что значит окончание сортировки.
3. РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ задачки
метод решения задачки максимально прост. Функция main() явлвется функцией меню и делает опрос клавиатуры . Зависимо от нажатой клавиши делает надлежащие деяния программки. Для чтения инфы о программке из файла text.hlp употребляется функция help(), которая работает с файловым выводом. Функция file() основная потому что с её помощью производится сортировка массива (вызов функций qqsort() и srecmg()) определение времени сортировки вызов функции построение гистограмм. Массив состоит из случайных чисел вводимых в него функцией генератора случайных чисел. Дальше функция file() вызывает надлежащие функции сортировки, засекает время сортировки подходящим методом , и вносит это время в массив simvol[]. Дальше данные из массива передаются в функцию grafix(), где они употребляются при выводе на экран гистограмм в графическом режиме . программка предугадывает случаи отсутствия неких программных частей. В этом случае вызывается функция Error(), которая создаёт окно сообщения в которое вписываются черта ошибки. Так программка не будет выполнятся если не найден файл “text.hlp” либо драйвер EGAVGA.BGI
.
3. РАЗРАБОТКА ПРОГРАММЫ
3.1 ОПИСАНИЕ ПРОГРАММЫ
Данная программка именуется “TEST” (имя исполняемого файла test.exe) и создана для анализа способов сортировки одномерного массива. программка работает на IBM совместимых компах семейства х86 начиная с 286 и выше, в операционной системе типа Ms-DOS 3.0 и выше.
программка содержит 5 главных функций: main(), file(), qsort(), srecmg(), grafix(). Все переменные, применяемые в программке являются локальными.
Функция main() содержит пункты меню и вызывает остальные исполняемые функции зависимо от нажатия предложеных многофункциональных кнопок F1, F2 и F10. Любая из этих функций работает автономно и независимо от 2-ух остальных.
программка реализована как в псевдографическом так и в графическом режиме (в связи с чем она может компилироваться лишь в DOSовских версиях BorlandC++ либо BorlandC). В графическом режиме она выводит на экран гистограмму которая охарактеризовывает время сортировки массивов 2-мя методами.
Программка употребляет как обычный так и файловый ввод-вывод инфы . Обычный ввод представлен запросом программки на ввод многофункциональных кнопок , которые задают нрав выполняемого деяния . Файловый ввод-вывод употребляется в функции help(), для вывода на экран инфы о разрабе программки , её многофункциональных кнопках и о вероятных ошибках в процессе выполнения. Не считая того программка работает с функцией времени clock() и переменными времени типа clock_t.
Так же программка содержит обычные функции языка Си, описанные в библиотеках: <string.h>, <stdlib.h>, <time.h>, <stdio.h>, <conio.h>,<graphics.h>. Ниже перечислены библиотеки с функциями и дано короткое описание использованных в программке обычных функций.
Из библиотеки <time.h>:
clock() – эта функция возвращает время , фиксируемое микропроцессором от начала счета программки , либо –1, есле оно не понятно . Для возврата этого времени в секундах применяется формула clock()/CLK_TCK.
Из библиотеки <stdlib.h>:
rand() – эта функция выдаёт псевдо случайное число в спектре от 0 до RAND_MAX не меньше 32767 .
exit() – вызывает обычное окончание программки .
Из библиотеки <stdio.h>:
printf() – эта функция производит вывод строчки на экран.
fopen() – эта функция открывает файл с данным именованием и возвращает поток либо NULL, если попытка открытия оказалась неудачной .
fclose() – эта функция производит дозапись ещё незаписанных буферизированных данных , сбрасывает нечитанный буферизированный ввод , высвобождает все автоматические запрошенные буфера , опосля что закрывает поток . Возвращает EOF в случае ошибки и 0 в неприятном случае .
fgetc() – эта функция возвращает следущуюлитеру из потока stream в виде unsignedchar либо EOF, если исчерпан файл либо найдена ошибка .
puts() – пишет стринг s и литеру новенькая – строчка в stdout . Возвращает EOF в случае ошибки , либо неотрицательное значение , если запись прошла нормально .
Из библиотеки <conio.h>
textbackground() – при помощи данной нам функции устанавливается цвет фона для функции cprintf().
textcolor() – при помощи данной нам функции устанавливается цвет текста для функции cprintf().
clrscr() – функция чистки экрана, цветом установленным функцией textbackground().
cprintf() – при помощи данной нам функции осуществляется вывод строчки с учётом цветов установленных функциями textbackground(), textcolor().
_setcursortype() – при помощи данной функции осуществляется изменение режима отображения курсора. Данных режимов в Си всего три – NOCURSOR (курсор выключен), SOLIDCURSOR (курсор в виде сплошного блока) NORMALCURSOR (обыденный курсор).
getch() – функция getch производит считывание первого единственного знака с клавиатуры, употребляется при считывании кнопок курсора при перемещении по окну выбора режима работы программки.
gotoxy() – эта функция перемещает курсор в подходящую часть экрана, обычно употребляется перед функцией cprintf().
В данной нам библиотеке описаны все символические константы цветов применяемые функциями textbackground(), textcolor(). В ней также описаны все типы курсоров применяемых функцией _setcursortype().
3.1.1 ОПИСАНИЕ ФУНКЦИИ main()
Функция main имеет тип void и является функцией меню. Main делает опрос клавиатуры и зависимо от нажатой многофункциональной клавиши производится соответственное действие (вызов помощи , тестирования и выход из программки). Эта возможность реализована благодаря конструкции множественного выбора switch . Функция имеет одну локальную переменную press имеющую тип char . Она принимает знак с клавиатуры без вывода на экран и употребляется в конструкции switch при переходе к иной выполняемой функции . В данной функции вызывается вспомогательная функция windows() , которая создаёт псевдографический интерфейс при запуске программки. При выбирании пт выхода из программки обычная функция textbackground() создаёт темный экран ,а функция exit() совершает выход из программки.
При вызове функции помощи (help()) программка обращается к данной нам функции, которая считывает и выводит информацию файловым методом. Вызываемый фаил хранится под именованием test.hlp и при его отсутствии выдаётся окно сообщения : «Фаил text.hlp не найден».
Вызов функции построения гистограмм производится при нажатии клавиши F2. При всем этом функция main() обращается к функции file() .
3.1.2 ОПИСАНИЕ ФУНКЦИИ srecmg().
Для построения упорядоченного перечня В’ из перечня В=<к1,к2,…,кn> при сортировке слиянием перечень В делится на n подсписков В1=<к1>, В2=<к2> , … , Вn=<кn> длины 1. Позже совершается процедура прохождения в какой m≥2 упорядоченных списков В1,В2,…,Вm изменяются на m/2 ( либо (m+1)/2) упорядоченных списков которые создаются слиянием B2i-1и B2i (2i≤m) и суммированием Bmc непарным m. процесс повторяется до возникновения одной последовательности длины m. количество действий , нужных для сортировки слиянием , равна nlog2n, поэтому что за одно прохождение производится n сравнений , а всего нужно выполнить log2n прохождений . Сортировка слияниием дастаточно отлично и употребляется при огромных значения n.
Функция srecmg() является рекурсивной , и сортирует массив а[n]. За каждым вызовом массив для сортировки делится на две части – от а[0] до
a[i-1] и от a[i] до a[n] , любая из которых сортируется раздельно , а позже производится их слияние. Слияние производится с помощью вызываемой функции merge() в которую передаётся указатель на массив , текущий номер элемента массива и количество частей массива . Параметрами функции merge() являются массив w[ ] ,его длина l/2 и длина первой части массива l1 .Функция merge() делает слияние подмассивов , образуя на их месте упорядоченный массив w[0],w[1],…,w[l2-2],w[l2-1] .
3.1.3 ОПИСАНИЕ ФУНКЦИИ qqsort()
Стремительная сортировка заключается в том , что перечень В=<k1,k2,…,kn> реорганизуется в B’,<k1>,B”,где В’ – подсписок В с элементами , не большенными k1 , а B” – подсписок В с элементами большенными k1. В перечне В’,<k1>,В” элемент К1 уже находится на месте где он должен быть в отсортированом перечне. Далее к перечням В’ и В’’ применяется упорядованичение резвой сортировкой .
Рекурсивная функция qqsort упорядоваечет резвой сортировкой участок масcива целых чисел 1-ый элемент которого указывается показателем v[left] , крайний – показателем v[right].
Если участок масива наиболее чем из 2-ух частей , v[left] – low >1,то находится делящий элемент и переносится в V[0]. Пременной last присваивается части, элементы которых соответственно больше и меньше last. Дальше функция делает перезапоминание делящего элемента и вызывает себя для разбитых подсписков .
Обмен частей производится с помощью функции swap() , в которую из функции qqsort() перелаётся указатель на массив и элементы , пространство-положение которых в массиве необходимо направить .
время построения перечня зависит от его исходного состояния. время будет наименьшим , если любой шаг раздела дает подсписки В’ , B’’ примерно схожей длины ; тогда нужно (nlog2 n) шагов . Если исходный перечень не много чем различается от обыденного отсортированного то нужно (n^2)/2 шагов . Стремительная сортировка просит доборной памяти порядка O (log2n) для выполнения рекурсивной функции qqsort() (неявного стэка).
3.1.4 ОПИСАНИЕ ФУНКЦИИ grafix()
Функция grafix() имеет тип void и параметр simbol[2] – массив скорости выполнения сортировки . Эта функция вызывается при построении гистограммы и работает в графическом режиме о чем информирует строчка initgraph(&gdriver, &gmode, «»), которая устанавливает систему в графический режим , описывает характеристику видеодрайвера. Если переменная errorcode не получает
Строчка:
bar3d(midx + otst + siz * n, midy -CopySimvol[n], midx + siz* (n+1 ), midy, 15, 1); создаёт 3D-изображения гистограмм, высота которых определяется массивом CopySimvol[n].
цвет выводимых частей изображения устонавливает функция setcolor(), а все выводимые полосы строятся функцией line(). текст выводится с помощью функции outtextxy(). Если текст должен выводиться вертикально то функции settextstyle() задаётся параметр VERT_DIR.
Опосля вывода на экран изображения производится опрос клавиатуры и если юзером была нажата кнопка “ESC”, то программка ворачивается в функцию file() и далее в функцию main(), где опять ждет нажатия нужной клавиши .
Функция closegraph() закрывает графический режим .
3.2 РУКОВОДСТВО ПРОГРАММИСТА
Данная программка создана для анализа способов сортировки массивов резвой и слиянием . программка может работать на IBM совместимых компах семейства х86 начиная с 286 и выше, под управлением операционных систем Ms-DOS 3.0 и выше и Windows 9x. Данная программка компилировалась с внедрением BorlandC++ 3.1.Компилия программки в версиях BorlandC++ сконфигурированных под Windows(таковых как BorlandC++4.5, BorlandC++5.2 и выше) не вероятна потому что графический режим [2] работает лишь в версиях сконфигурированных под DOS.
программка не просит от пользоватля ввода массива для его сортировки. Этот массив создается специальной функцией языка Си – генератор случайных чисел[3]. Программка была разработана на компьюторе с низкой тактовой частотой(75MГц). А потому что в программке употребляется секундомер, то тактовая частота компьютора, на котором показывается программка, влияет на точность выводимых результатов. Потому не советуется воспользоваться ею на компьюторах с тактовой частотой выше 150МГц. Хотя в неприятном случае скорость сортировки значиельно возрастает.
Листинг программки приведён в приложении 1.
программка не предусмотренна для работы в режиме командной строчки. Если вводимая юзером многофункциональная кнопка не предусмотренна программкой, то она производиться не будет до того времени, пока юзер не введет соответственный знак. Если программка не находит неких подходящих для ее выполнения файлов, то выдается окно сообщения о ошибке с текстом предпосылки. Функция error() вызывается всюду, где возникает ошибка.(делает окно сообщения). В случае необходимости программку можно приостановить в любом месте её выполнения последующими комбинациями кнопок: Ctrl
C
либо Alt
X
.
Вызов программки осуществляется путём пуска файла test.exe, при всем этом программка будет работать в интерактивном режиме.
Окно помощи программки содержит: заглавие программки, данные о разрабе, предназначение, многофункциональные клавиши применяемые в программке, и вероятные задачи при ее выполнении.
3.3 РУКОВОДСТВО ОПЕРАТОРА
Главный функцией данной программки является определение времени сортировки массивов способами резвой и слиянием. Методом незначимых конфигураций в программке, можно приспособить программку специально для сортировки массивов. Данная программка (test.exe) является единым исполняемым модулем и не просит наличия всех остальных установленных программных средств. Она так же не просит установки на комп, любых специфичных аппаратных средств.
Контрольный пример выполнения программки приведён в приложении 2.
программка может работать только в интерактивном режиме. Сортировка массива с огромным числом элементом на современном компе займет всего несколько секунд и зависит от размера сортируемого массива.
Опосля загрузки программки оператору будет предложено надавить нужную кнопку для продолжения выполнения программки , для вывода инфы о программке либо для выхода. Если программка не содержит файла text.hlp либо не найдан драйвер EGAVGA.BGI, то программка выдаёт окно сообщения о ошибке. Если программка содержит все нужные элементы, то она выдаст окно сообщния о способности выполнения анализа сортировки. Если программка получила разрешение на начало процесса сортировки, то она делает его и опосля окончания выводит на экран в графическом режиме результаты о анализе сортировок. В случае необходимости программку можно приостановить в любом месте её выполнения последующими комбинациями кнопок: Ctrl
C
либо Alt
X
. В таком случае программка не выполнит ни каких действий.
Окно помощи программки содержит: заглавие программки, данные о разрабе, предназначение, многофункциональные клавиши применяемые в программке, и вероятные задачи при ее выполнении.
ЗАКЛЮЧЕНИЕ
В итоге выполнения курсового проекта была написана программка, анализирующая сортировку массивов методами резвой и слиянием. программка владеет высочайшим параметром быстродействия, небольшим размером и не требовательна к системным ресурсам компа. В качестве недочета программки можно отнести то, что точность выполнения программки зависит от тактовой частоты компа. Этот недочет можно решить путём конфигурации количества сортируемых частей массива. Программка быть может преобразована для использования в целях сортировки массивов вводимых юзером.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Шолмов Л.И. Управление по турбо Си. М.: Наука, 1994. – 94-98с.
2. Уинер Р. язык Турбо Си : Пер. с англ. -М.:: мир, 1991. – 384 с.
3. Керниган Б.В, Ричи Д.М. Си для экспертов. М.: Энергия, 1996.– 213 с.
4. Грейд Дж. Математическое программирование. М.: Наука, 1987. – 241 с.
5. Либерман М. методы сортировки массивов. М.: Наука, 1997. – 43-81с.
приложение 1
ЛИСТИНГ ПРОГРАММЫ
// листинг программки сортировки массивов разработанная Андрусевичем Б.И.
#include <stdio.h>
#include <dos.h>
#include <graphics.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <time.h>
//————-< Создание оболочки >————-
void windows(int w)
{
int n;
_setcursortype(0);
window(1, 1, 80, 25); // Выделениеокна
textbackground(BLACK); // Цветфона
clrscr(); // Чистка экрана
window(1, 25, 80, 25); // Выделение окна
textbackground(GREEN); // Цвет фона
clrscr(); // Чистка экрана
window(1, 25, 80, 25);
textcolor(BLACK); // цвет текста
if (w == 1) // Проверка на выбор окна
{
n = 21;
cprintf(» Помощь Тест Выход»);
window(2, 25, 4, 25);
textcolor(RED); // Управляющие клавиши
cprintf(«F1»); // основного окна
window(13, 25, 15, 25);
cprintf(«F2»);
window(22, 25, 25, 25);
cprintf(«F10»);
textbackground(BLUE);
}
else
{
n =22;
cprintf(» Выходизпомощи «);
window(3, 25, 6, 25);
textcolor(RED); // Управляющиеклавиши
cprintf(«Esc»); // окнапомощи
textbackground(CYAN);
}
window(1, 1, 80, 25); // Прорисовкарамки
textcolor(WHITE);
cprintf(«+———————————— тест ————————————+»);
for (int k = 0; k < n; k++)
cprintf(«¦ ¦»);
cprintf(«+——————————————————————————+»);
if (w == 1)
{
window(2, 2, 79, 2);
puts(» Эта программка показывает сортировку массива 2-мя способами:»);
window(2, 3, 79, 3);
puts(» резвым способом и способом слияния. Опосля что определяется время сор-«);
window(2, 4, 79, 4);
puts(» тировки массива каждым способом и итог выводится в виде гисто-«);
window(2, 5, 79, 5);
puts(» гр.»);
window(2, 6, 79, 6);
window(20, 10, 60, 15);
textcolor(WHITE);
textbackground(LIGHTGRAY);
cprintf(«+——————————————————————+»);
cprintf(«¦ НЕОБХОДИМЫЕ ФАЙЛЫ ПРИСУТСТВУЮТ ¦»);
cprintf(«¦ (для тестировния нажмите F2) ¦»);
cprintf(«+——————————————————————+»);
closegraph();
}
}
//————< Окно сообщения ошибок>————
void Error()
{
window(20, 10, 60, 15);
textcolor(WHITE);
textbackground(LIGHTGRAY);
cprintf(«+—————— Ошибка —————-+»);
cprintf(«¦ ¦ «);
cprintf(«¦ ¦»);
cprintf(«¦ ¦»);
cprintf(«+———————————————+»);
}
//————-< Функцияпомощи >—————-
help()
{
int n = 1;
FILE *hl; // Указатели на файл
char string[78];
if ((hl = fopen(«test.hlp», «r»)) != NULL) // Проверка на открытие файла
{
windows(0);
window(2, 2, 78, 23);
textcolor(BLACK);
while (fgets(string, 78, hl) != NULL && n < 23)
{
gotoxy(1, n++); // Построчный вывод файла
cputs(string); // помощи
}
window(36, 1, 44, 1);
printf(» Помощь «); // Вывод заголовка помощи
while (27 != getch());
}
else{
Error();
window(29, 12, 52, 12);
textcolor(BLACK);
cprintf(«файл TEST.HLP ненайден»);
getch();
windows(1);
}
fclose(hl);
windows(1);
return 0;
}
//———< Функцияпостроениягистограмм>——-
grafix(double simvol[2])
{
double CopySimvol[2]; // Масивколичествасимволов
long float max = 0;
int gdriver = DETECT, gmode, errorcode;
int midx = 50; // Обявление переменных
int midy = 410; // с заданними исходными
int i, s; // значениями
int siz = 100;
int otst = 10;
int rovn = 45;
char chis[2];
char buf[10];
initgraph(&gdriver, &gmode, «»);
errorcode = graphresult(); // Записькодошибки
if (errorcode != grOk) // Проверканаошибку
{
Error(); // Вызовфункцииокна
window(26, 12, 54, 12);
textcolor(BLACK);
cprintf(«драйвер EGAVGA.BGI ненайден»);
getch();
windows(1);
return 0;
}
for (int y = 0; y < 2; y++) // Оприделениемаксимального
if (max < simvol[y]) // числа
max = simvol[y];
for (int b = 0; b < 2; b++) // Оприделениевысотыстолбцов
CopySimvol[b] = simvol[b] * 200 / max;
setfillstyle(CLOSE_DOT_FILL,9);
for (int n = 0; n < 2; n++) // Построениестолбцовилиний
{
setcolor(BLUE);
bar3d(midx + otst + siz * n, midy — CopySimvol[n], midx + siz* (n+1 ), midy, 15, 1);
setcolor(BROWN);
line(midx + rovn + siz * n, midy + otst, midx + rovn + siz * n, midy + otst * 2);
sprintf(chis, «%d», n + 1);
setcolor(GREEN);
outtextxy((midx + rovn + siz * n) — 2, midy + otst * 2, chis);
setcolor(CYAN);
sprintf(buf, «%lf», simvol[n]);
outtextxy((midx + rovn + siz * n) — 15, midy — CopySimvol[n] — rovn, buf);
}
setcolor(BROWN);
line(midx, 100, midx, midy + otst); // Построениеоси Y
line(midx, midy + otst, 280, midy + otst); // Построениеоси X
line(midx — otst, midy — 200, midx, midy — 200); // Построение
line(midx — otst, midy — 100, midx, midy — 100); // полосы
settextstyle(DEFAULT_FONT, HORIZ_DIR, 1);
setcolor(GREEN);
outtextxy(535, 460, «ESC «);
outtextxy(10, 205, «100»);
outtextxy(10, 305, «50»);
outtextxy(350, 235, «1. Сортирвка массива резвым»);
outtextxy(350, 250, » способом»);
outtextxy(350, 280, «2. Сортирвка массива способом»);
outtextxy(350, 295, » слияния»);
setcolor(LIGHTBLUE);
outtextxy(300, 423, «способ«);
outtextxy(570, 460, «Выход»);
settextstyle(DEFAULT_FONT, HORIZ_DIR, 2);
outtextxy(220, 30, «гистограмма«);
settextstyle(DEFAULT_FONT, VERT_DIR, 1);
outtextxy(48, 160, «время«);
while (27 != getch()); // Проверка на знак ESC
closegraph();
windows(1);
return 0;
}
/*qsort:сортирует v[left]…v[right] повозрастанию*/
void qqsort( int v[], int left, int right)
{
int i,last;
delay(1);
void swap( int v[], int i, int j);
if(left>=right) /*ничего не делается если*/
return; /* в массиве наименее 2-ух эл-тов */
swap(v,left,(left+right)/2); /*делящий эл-нт переносится в v[0]*/
last=left;
for(i=left+1;i<=right;i++) /*делениеначасти*/
if(v[i]<v[left])swap(v,++last,i);
swap(v,left,last); /*перезапоминается делящий элемент*/
qqsort(v,left,last-1);
qqsort(v,last+1,right);
}
void swap( int v[], int i, int j)
{
long int temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
/*SRECMG — РЕКУРСИВНАЯ СОРТИРОВКА СЛИЯНИЕМ*/
void srecmg(a,n)
int a[],n;
{
void merge( int*, int, int);
int i;
delay(1);
if(n>1)
{i=n/2;srecmg(a,i);srecmg(a+i,n-i);merge(a,i,n);}
}
/*merge—слияниедвухподсписков*/
#define MAX(x,y) ((y)<(x)?(x):(y))
void merge( int*w, int l1, int l2)
{
int*a,*pa,*pb,i;
a=( int*)calloc(l2+2,sizeof( int));
pa=a;pb=a+l1+1;
for(i=0;i<l1;i++) *pa++=w[i];
for(i=l1;i<l2;i++) *pb++=w[i];
*pa=*pb=MAX(w[l1-1],w[l2-1])+1;
pa=a;pb=a+l1+1;
for(i=0;i<l2;i++)
w[i]=(*pa<*pb?*pa++:*pb++);
free(a);
}
#define ww 700
//——-< Функция вызова различных способов >——-
file()
{ void qqsort( int *, int,int);
void srecmg( int*, int);
double simvol[2];
int s;
clock_t start,start2,end,end2; int t=0;
int gener1[ww],gener2[ww]; //генератор случайных чисел
randomize(); //Устанавливает генератор в 0
for ( s=0 ; s < ww ; s++)
{ gener1[s]= ( rand()%100 ); // rand()-функциягенератора
gener2[s] =gener1[s];
}
{ start=clock();
qqsort(gener1,0,ww-1);
end=clock();
simvol[0] = ((end — start)/CLK_TCK);
}
{ start2 =clock();
srecmg(gener2,ww);
end2=clock();
simvol[1] = ((end2 — start2)/CLK_TCK);
}
grafix(simvol); // Вызов функции построения гистограмм
windows(1);
return 0;
}
//——————-< Меню >———————
void main()
{
char press;
windows(1);
while (1)
{
press = getch(); // Опросклавиатуры
switch(press)
{
case 59: help(); break; // Вызовпомоши
case 60: file(); break; // Пуск гистограммы
case 68: { // Выход из программки
window(1, 1, 80, 25);
textbackground(BLACK);
clrscr();
exit(1);
} } }}
приложение 2
КОНТРОЛЬНЫЙ ПРИМЕР ВЫПОЛНЕНИЯ ПРОГРАММЫ
В качестве примера возьмём начальный файл “Test.exe” и запустим его . На дисплее возникает окно собщения о наличии нужных файлов. Для продолжения выполнения программки юзер надавливает кнопку F
2
, в итоге что на дисплее возникает гистограмма , характеризующая скорость выполнения сортировки массивов. Воспользовавшись кнопкой Esc
, юзер выходит с графического режима в режим отображения меню. При нажатии юзером клавиши F
1
на дисплее возникает окно помощи которое содержит заглавие программки, данные о разрабе, предназначение, многофункциональные клавиши применяемые в программке, и вероятные задачи при ее выполнении.Нажатие клавиши Esc
приводит к закрытию окна помощи. Для выхода из программки юзер должен надавить кнопку F
10
.
Пример выводимой гистограммы.]]>