МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ХЕРСОНСКИЙГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
рАЗРАБОТКА ПРОГРАММЫ ДЛЯ
Анализа методов сортировки одномерных массивов.
Курсовой проект
подисциплине «Программирование»
Пояснительная записка
Исполнитель
студент группы 2КСС3 ________________________
(подпись, дата)
Руководитель
старшийпреподаватель ________________________
(подпись, дата)
Нормоконтролер
старший преподаватель_________________________
(подпись, дата)
РЕФЕРАТ
Курсовой проект содержит: стр. – 39 машинописноготекста, литературных источников – 5, приложения – 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 — число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаютсявправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов. Присоединение новых элементов к выходному файлу происходиткак справа, так и слева от центрального элемента с возможным сдвигом вправоили влево.
Время работыалгоритма 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 703765 897 908
Время работы алгоритма t примерно оценивается формулой: t=a*N**b
где a и b — неизвестные константы, зависящие от программнойреализа-
ции алгоритма.
Вставки в связанный список
Среди общих способов улучшенияалгоритма простых вставок можно рассмотреть способ, основанный на измененииструктуры данных. Сортировка простыми вставками состоит из двух основныхопераций:
— просмотра исходного файла со сравнением переменной Х с
элементами 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] на следующий элемент списка. Значение L[i]=0 соответствует последнему элементу в списке, указатель B[1] указывает на начало первогоподсписка и одновременно на начало всего списка. Через minK обозначено минимальное значениеключа в файле, через М — среднее выбранное значение количества элементов вподсписке. d — номертекущего списка, в который должен быть вставлен элемент K[j]. Величина R=MAX/Q есть диапазон значений ключей,приходящийся на один список.
Время работы алгоритма t примерно оценивается формулой: t=a*NЅ + b*N
где a,b — неизвестные константы, зависящие от программной реализации алгоритма.
Обменная сортировка
Название этой группы методовпроизошло от основного типа операций, используемого в алгоритмах — обмен двухэлементов в файле своими значениями. Эта операция используется и в другихгруппах, поэтому классификацию нельзя признать вполне строгой, но данное разделение тем не менее является традиционным. Файл, подлежащий сортировке,в общем случае состоит из элементов-записей, включающих информационнуючасть и ключи, по которым производится упорядочение по возрастанию.
Поскольку информационная частьпочти не влияет на процесс сортировки, будем предполагать, что файлы,используемые в примерах, состот только из элементов-ключей, а информационнаячасть записи отсутствует.
Метод пузырька
Алгоритм довольно очевиден.
Пары стоящих рядом элементовпросматриваются в направлении снизу вверх и сравниваются. Если верхний элементоказывается меньше нижнего, то они меняются местами. Продолжая этот процесс циклически, мы в конце концов придем к отсортированному файлу.Файл расположенвертикально снизу вверх, чтобы эффект всплывающего пузырька выглядел болеенаглядно. Элементы с большим значением ключа «всплывают» наверх, после последовательных сравнивнений с соседними элементами.
Время работы алгоритма t примерно оцениваетсяформулой: t=a*NЅ + b*N
где a,b — неизвестные константы, зависящие от программнойреализа-
ции алгоритма.
Модификация метода пузырька
Модификация метода пузырькасостоит в том, что файл можно просматривать как с начала до конца, так и сконца до начала попеременно. Это несколько сокращает число перемещенийэлементов.
Время работы алгоритма t примерно оценивается формулой: t=a*NЅ + b*N
где a,b — неизвестные константы,зависящие от программной реализации алгоритма.
Быстрая сортировка.
Основная стратегия ускоренияалгоритмов сортировка — обмены между как можно более дальними элементамиисходного файла — в методе быстрой сортировки реализована за счет того, чтоодин из ключей в исходном файле используется для разделения его на два подфайлатак, чтобы слева от выбранного элемента находились только элементы с меньшимиключами, а справа — только с большими. Элемент, разделяющий файл, помещаетсямежду его двумя подфайлами и процедура выполняется рекурсивно для каждойполовины до тех пор, пока в очередном новом подфайле не окажется меньше, чем Мэлементов, где М — заранее выбранное число.
Сортировка подфайлов, содержащихменьше чем М элементов, выполняется каким-либо простым методом, напримерпростыми вставками. Таким образом, реализация метода зависит от двухпараметров: значения М и способа выбора элемента, который предназначен дляразделения файла на две части.
Блок выбора Х в простейшемслучае формулируется как X=K[l], однако это может привести к крайненеэффективному алгоритму. Наиболее простое лучшее решение — выбирать Х какслучайный ключ из диапазона K[l]… K[r] и обменять его с K[l].
Время работы алгоритма t примерно оценивается формулой:
t=a*N*logN + b*N
где a,b — неизвестные константы,зависящие от программной реализации алгоритма.
Обменная поразрядная сортировка
Данный метод использует двоичноепредставление ключей. Файл сортируется последовательно по битам двоичногопредставления ключей, начиная со старшего. Ключи, имеющие значение данногобита, равноенулю, ставятся в левую половину файла, а ключи со значением бита 1в правую. Функция b(ключ)возвращает значение ьита с номером b аргумента, m-максимальное количество значащих битов в ключах.
Время работы алгоритма 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 — неизвестные константы, зависящие от программной реализации алгоритма.
Сортировка посредством слияния
Алгоритмы сортировки этого класса основываются на объединении нескольких (часто двух) уже упорядоченнхфайлов. Рассмотренные далее алгоритмы выбирают из исходного файла упорядоченныеотрезки и объединяют их в более длинные.
Естественное двухпутевоеслияние
Этот алгоритм ищет упорядоченныеотрезки с двух концов файла ипереписывает их по очереди также в оба конца.Повторяя эту процедуру в цикле, мы приходим к середине файла, что означаетокончание сортировки.
Элементы файла пересылаются изодной области в другую, меняя направление пересылки. Для запоминаниянаправления пересылки служит переменная s, принимающая значения TRUE и FALSE попеременно. Другой логическийпризнак f служит сигналомпродолжения-окончания алгоритма, если все области слились в конце концов водну. Переменная d принимаетпопеременно значения +1 -1 и указывает направление просмотра файла: вперед или назад.Операция обозначает обмен значениями двух переменных. Операция Џ обозначает инверсию логической переменной или выражения.
Время работы алгоритма 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г. Предложенная версия быстрой сортировки, разумеется , не самая быстрая среди всех возможных, но зато она из самых простых .
Основная стратегия ускоренияалгоритмов сортировки — обмены между как можно более дальними элементамиисходного файла — в методе быстрой сортировки реализована за счет того, чтоодин из ключей в исходном файле используется для разделения его на два подфайлатак, чтобы слева от выбранного элемента находились только элементы с меньшимиключами, а справа — только с большими.
Алгоритмы сортировки методомслияния основываются на объединении нескольких (часто двух) ужеупорядоченнх файлов. Этот алгоритм ищет упорядоченные отрезки с двух концов файла и переписывает их по очереди также в оба конца. Повторяя этупроцедуру в цикле, мы приходим к середине файла, что означает окончаниесортировки.
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-DOS3.0 и выше.
Программа содержит пять основных функций: main(),file(), qsort(), srecmg(), grafix(). Все переменные, используемые в программе являютсялокальными.
Функция main() содержит пункты меню ивызывает другие исполняемые функции в зависимости от нажатия предложеныхфункциональных клавиш F1, F2 и F10. Каждая из этих функций работает автономно инезависимо от двух других.
Программа реализована как в псевдографическом так и вграфическом режиме (в связи с чем она может компилироваться только в DOSовскихверсиях BorlandC++ или BorlandC). В графическом режиме онавыводит на экран гистограмму которая характеризует время сортировки массивовдвумя способами.
Программа использует как стандартный так и файловыйввод-вывод информации. Стандартный ввод представлен запросом программы на вводфункциональных клавиш, которые задают характер выполняемого действия.Файловый ввод-вывод используется в функции help(), длявывода на экран информации о разработчике программы, её функциональныхклавишах и о возможных ошибках в процессе выполнения. Кроме того программа работаетс функцией времени clock() и переменными времени типа clock_t.
Так же программа содержит стандартные функции языкаСи, описанные в библиотеках: , ,, , ,. Ниже перечислены библиотеки с функциями и данократкое описание использованных в программе стандартных функций.
Из библиотеки :
clock()– эта функция возвращает время, фиксируемое процессором от начала счетапрограммы, или –1, есле оно не известно. Для возвращения этого времени в секундахприменяется формула clock()/CLK_TCK.
Из библиотеки :
rand() – эта функция выдаёт псевдо случайное число вдиапазоне от 0 до RAND_MAX не меньше 32767 .
exit()– вызывает нормальное завершение программы.
Из библиотеки :
printf()– эта функция осуществляет вывод строки на экран.
fopen()– эта функция открывает файл с заданным именем и возвращает поток или NULL,если попытка открытия оказалась неудачной .
fclose()– эта функция производит дозапись ещё незаписанных буферизированных данных,сбрасывает нечитанный буферизированный ввод, освобождает все автоматическиезапрошенные буфера, после чего закрывает поток. Возвращает EOF вслучае ошибки и 0 в противном случае .
fgetc()– эта функция возвращает следущуюлитеру из потока stream в виде unsigned char или EOF, если исчерпан файл или обнаружена ошибка .
puts()– пишет стринг s и литеру новая – строка в stdout.Возвращает EOF в случае ошибки, или неотрицательное значение,если запись прошла нормально.
Из библиотеки
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().
Для построения упорядоченного списка В’ из спискаВ= при сортировке слиянием список В делится на nподсписков В1=, В2=,…, Вn=длины 1. Потом совершается процедура прохождения в которой m≥2упорядоченных списков В1, В2,..., Вm меняются на m/2 (или (m+1)/2) упорядоченных списков которые создаютсяслиянием B2i-1и B2i (2i≤m) и суммированием Bm c непарным m. Процесс повторяется до появленияодной последовательности длины m. Количество действий, необходимых для сортировкислиянием, равна n log2n, потому что заодно прохождение выполняется 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()
Быстрая сортировка состоит в том, что список В=реорганизуется в B’,,B”, где В’ – подсписок В с элементами, не большими k1,а B” – подсписок В с элементами большими k1. Всписке В’,, В” элемент К1 уже находится на месте где ондолжен быть в отсортированом списке. Дальше к спискам В’ и В’’ применяетсяупорядованичение быстрой сортировкой .
Рекурсивная функция qqsort упорядоваечет быстрой сортировкой участок масcивацелых чисел первый элемент которого указывается показателем v[left], последний – показателем v[right].
Если участок масива более чем из двух элементов, v[left]– low >1, то находится делящий элемент и переносится в V[0].Пременной last присваивается значение первого элемента массива left.Затем массив делится на две части, элементы которых соответственно больше именьше last. Далее функция выполняет перезапоминание делящегоэлемента и вызывает себя для разбитых подсписков .
Обмен элементов выполняется при помощи функции swap(), в которую из функции qqsort() перелаётся указатель на массив и элементы,место-положение которых в массиве нужно обратить .
Время построения списка зависит от его начальногосостояния. Время будет минимальным, если каждый шаг раздела дает подсписки В’, B’’ приблизительно одинаковой длины; тогда необходимо(n log2 n) шагов. Если начальный список мало чем отличается отобычного отсортированного то необходимо (n^2)/2 шагов.Быстрая сортировка требует дополнительной памяти порядка O (log2n)для исполнения рекурсивной функции qqsort() (неявного стэка).
3.1.4 ОПИСАНИЕ ФУНКЦИИ grafix()
Функция grafix() имеет тип voidи параметр simbol[2] – массив скорости выполнения сортировки. Этафункция вызывается при построении гистограммы и работает в графическом режиме очем информирует строка initgraph(&gdriver, &gmode,""), которая устанавливаетсистему в графический режим, определяет характеристику видеодрайвера. Еслипеременная errorcode не получает значение grOk, тодальнейшее выполнение программы не возможно так как графический режим неустановлен (о чем выводится сообщение). В массиве simvol[]определяется больший элемент, столбец которого устанавливается в 100%.
Строка:
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.Данная программа компилировалась с использованием Borland C++ 3.1.Компилия программы в версиях Borland C++ сконфигурированных под Windows(таких как Borland C++4.5, Borland C++5.2 и выше) не возможна так как графический режим [2]функционирует только в версиях сконфигурированных под DOS. Программа не требует от пользоватля ввода массивадля его сортировки. Этот массив создается специальной функцией языка Си – генераторслучайных чисел[3].Программа была разработана на компьюторе с низкой тактовой частотой(75MГц). А так как в программеиспользуется секундомер, то тактовая частота компьютора, на которомдемонстрируется программа, влияет на точность выводимых результатов. Поэтому несоветуется пользоваться ею на компьюторах с тактовой частотой выше 150МГц. Хотяв противном случае скорость сортировкизначиельно увеличивается.Листинг программыприведён в приложении 1.Программа непредусмотренна для работы в режиме командной строки. Если вводимая пользователем функциональная клавиша не предусмотренна программой, то онавыполняться не будет до тех пор, пока пользователь не введет соответствующийсимвол. Если программа не находит некоторых нужных для ее выполнения файлов, товыдается окно сообщения об ошибке с текстом причины. Функция error() вызывается везде, где появляетсяошибка.(создает окно сообщения). В случае необходимости программу можноостановить в любом месте её исполнения следующими комбинациями клавиш: CtrlCили AltX.
Вызов программы осуществляется путём запуска файлаtest.exe, при этом программа будет работать в интерактивном режиме.
Окно помощипрограммы содержит: название программы, данные о разработчике, назначение,функциональные клавиши используемые в программе, и возможные проблемы при еевыполнении.
3.3 РУКОВОДСТВО ОПЕРАТОРАОсновной функцией данной программыявляется определение времени сортировки массивов методами быстрой и слиянием.Путем незначительных изменений в программе, можно приспособить программу специальнодля сортировки массивов. Данная программа (test.exe)является единым исполняемым модулем и не требует наличия любых другихустановленных программных средств. Она так же не требует установки накомпьютер, каких бы то ни было специфических аппаратных средств.Контрольный примервыполнения программы приведён в приложении 2.Программа может работатьлишь в интерактивном режиме. Сортировка массива с большим числом элементом на современном компьютере займет всего несколько секунд и зависит от размерасортируемого массива.После загрузки программыоператору будет предложено нажать необходимую клавишу для продолжениявыполнения программы, для вывода информации о программе или для выхода. Еслипрограмма не содержит файла text.hlp или не найдан драйвер EGAVGA.BGI, то программа выдаёт окно сообщения об ошибке. Еслипрограмма содержит все необходимые элементы, то она выдаст окно сообщния овозможности выполнения анализа сортировки. Если программа получила разрешениена начало процесса сортировки, то она выполняет его и после завершения выводитна экран в графическом режиме результаты о анализе сортировок. В случаенеобходимости программу можно остановить в любом месте её исполнения следующимикомбинациями клавиш: CtrlCилиAltX. В таком случае программа невыполнит ни каких действий.
Окно помощипрограммы содержит: название программы, данные о разработчике, назначение,функциональные клавиши используемые в программе, и возможные проблемы при еевыполнении.
ЗАКЛЮЧЕНИЕ
В результате выполнения курсового проекта быланаписана программа, анализирующая сортировку массивов способами быстрой ислиянием. Программа обладает высоким параметром быстродействия, маленькимразмером и не требовательна к системным ресурсам компьютера. В качественедостатка программы можно отнести то, что точность выполнения программызависит от тактовой частоты компьютера. Этот недостаток можно решить путёмизменения количества сортируемых элементов массива. Программа может бытьпреобразована для использования в целях сортировки массивов вводимыхпользователем.
СПИСОКИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Шолмов Л.И. Руководство по турбоСи. М.: Наука, 1994. – 94-98с.
2. Уинер Р. Язык Турбо Си: Пер. сангл. -М.:: Мир, 1991. – 384 с.
3. Керниган Б.В, Ричи Д.М. Си дляпрофессионалов. М.: Энергия, 1996.– 213 с.
4. Грейд Дж. Математическоепрограммирование. М.: Наука, 1987. – 241 с.
5. Либерман М. Алгоритмы сортировкимассивов. М.: Наука, 1997. – 43-81с.
Приложение1
ЛИСТИНГ ПРОГРАММЫ
// листингпрограммы сортировки массивов разработанная Андрусевичем Б.И.
#include
#include
#include
#include
#include
#include
#include
//--------------------------
voidwindows(int w)
{
intn;
_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
cprintf("¦ ¦");
cprintf("+------------------------------------------------------------------------------+");
if(w == 1)
{
window(2,2, 79, 2);
puts(" Эта программа демонстрирует сортировкумассива двумя методами:");
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();
}
}
//-----------------------
voidError()
{
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
{
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);
return0;
}
//---------------
grafix(doublesimvol[2])
{
doubleCopySimvol[2]; // Масив количества символов
longfloat max = 0;
intgdriver = DETECT, gmode, errorcode;
int midx = 50; //Обявление переменных
int midy =410; // с заданними начальными
int i, s; // значениями
intsiz = 100;
intotst = 10;
introvn = 45;
charchis[2];
charbuf[10];
initgraph(&gdriver,&gmode, "");
errorcode= graphresult(); // Запись код ошибки
if(errorcode != grOk) // Проверка на ошибку
{
Error(); // Вызов функции окна
window(26,12, 54, 12);
textcolor(BLACK);
cprintf(«Драйвер EGAVGA.BGI не найден»);
getch();
windows(1);
return0;
}
for(int y = 0; y
if(max
max= simvol[y];
for(int b = 0; b
CopySimvol[b]= simvol[b] * 200 / max;
setfillstyle(CLOSE_DOT_FILL,9);
for(int n = 0; 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);
return0;
}
/*qsort: сортирует v[left]...v[right] по возрастанию*/
voidqqsort( int v[], int left, int right)
{
inti,last;
delay(1);
voidswap( int v[], int i, int j);
if(left>=right) /*ничего не делается если*/
return; /* в массиве менее двух эл-тов */
swap(v,left,(left+right)/2); /*делящий эл-нт переносится в v[0]*/
last=left;
for(i=left+1;i
if(v[i]
swap(v,left,last); /*перезапоминается делящий элемент*/
qqsort(v,left,last-1);
qqsort(v,last+1,right);
}
voidswap( int v[], int i, int j)
{
longint temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
/*SRECMG-- РЕКУРСИВНАЯ СОРТИРОВКА СЛИЯНИЕМ*/
voidsrecmg(a,n)
int a[],n;
{
voidmerge( int*, int, int);
inti;
delay(1);
if(n>1)
{i=n/2;srecmg(a,i);srecmg(a+i,n-i);merge(a,i,n);}
}
/*merge--слияние двух подсписков*/
#defineMAX(x,y) ((y)
voidmerge( 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
for(i=l1;i
*pa=*pb=MAX(w[l1-1],w[l2-1])+1;
pa=a;pb=a+l1+1;
for(i=0;i
w[i]=(*pa
free(a);
}
#define ww700
//--------------
file()
{void qqsort( int *, int,int);
void srecmg( int*, int);
doublesimvol[2];
int s;
clock_tstart,start2,end,end2; int t=0;
int gener1[ww],gener2[ww]; //Генератор случайных чисел
randomize(); //Устанавливает генератор в 0
for (s=0; 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);
return0;
}
//---------------------------------------
voidmain()
{
charpress;
windows(1);
while(1)
{
press = getch(); // Опрос клавиатуры
switch(press)
{
case59: help(); break; // Вызов помоши
case 60: file(); break; // Запускгистограммы
case68: { // Выход из программы
window(1, 1, 80, 25);
textbackground(BLACK);
clrscr();
exit(1);
} } }}
Приложение2
КОНТРОЛЬНЫЙ ПРИМЕР ВЫПОЛНЕНИЯ ПРОГРАММЫ
В качестве примера возьмём исходный файл “Test.exe” и запустим его. На экране появляется окно собщения о наличии необходимыхфайлов. Для продолжения выполнения программы пользователь нажимает клавишу F2, в результате чего на экранепоявляется гистограмма , характеризующая скорость выполнения сортировкимассивов. Воспользовавшись клавишей Esc,пользователь выходит с графического режима в режим отображения меню. Принажатии пользователем клавиши F1 на экране появляется окно помощи которое содержитназвание программы, данные о разработчике, назначение, функциональные клавишииспользуемые в программе, и возможные проблемы при ее выполнении.Нажатиеклавиши Esc приводит к закрытию окна помощи. Для выхода изпрограммы пользователь должен нажать клавишу F10./> />
Пример выводимой гистограммы.