Анализ методов сортировки одномерного массива - Курсовая работа

Во многих случаях программы, написанные на Си, сравнимы по скорости с программами, написанными на языке ассемблера[2]. Си сочетает эффективность и мощность в относительно малом по размеру языке. Хотя Си не содержит встроенных компонент языка, выполняющих ввод-вывод, распределение памяти, манипуляций с экраном или управление процессами, тем не менее, системное окружение Си располагает библиотекой объектных модулей[3], в которой реализованы подобные функции. Язык Си не является ни языком "очень высокого уровня", ни "большим" языком, и не предназначается для некоторой специальной области применения, но отсутствие ограничений и общность языка делают его более удобным и эффективным для многих задач, чем языки, предположительно более мощные.Время работы алгоритма t примерно оценивается формулой: t=a*NЅ b*N где a,b - неизвестные константы, зависящие от программной реализации алгоритма. Это означает, что сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2 1 и j и т.д. Время работы алгоритма t примерно оценивается формулой: t=a*NЅ b*N c*N*LOGN где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма. Время работы алгоритма t примерно оценивается формулой: t=a*NЅ b*N где a,b - неизвестные константы, зависящие от программной реализации алгоритма. Время работы алгоритма t примерно оценивается формулой: t=a*NЅ b*N c*N*LOGN где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма.Метод быстрой сортировки был предложен К. А. Р. Основная стратегия ускорения алгоритмов сортировки - обмены между как можно более дальними элементами исходного файла - в методе быстрой сортировки реализована за счет того, что один из ключей в исходном файле используется для разделения его на два подфайла так, чтобы слева от выбранного элемента находились только элементы с меньшими ключами,а справа - только с большими.Функция main() явлвется функцией меню и выполняет опрос клавиатуры . Для чтения информации о программе из файла text.hlp используется функция help(), которая работает с файловым выводом. Функция file() основная так как с ее помощью выполняется сортировка массива (вызов функций qqsort() и srecmg()) определение времени сортировки вызов функции построение гистограмм.Файловый ввод-вывод используется в функции help(), для вывода на экран информации о разработчике программы , ее функциональных клавишах и о возможных ошибках в процессе выполнения. Из библиотеки : clock() - эта функция возвращает время , фиксируемое процессором от начала счета программы , или-1, есле оно не известно . Из библиотеки : printf() - эта функция осуществляет вывод строки на экран. fopen() - эта функция открывает файл с заданным именем и возвращает поток или NULL, если попытка открытия оказалась неудачной . fclose() - эта функция производит дозапись еще незаписанных буферизированных данных , сбрасывает нечитанный буферизированный ввод , освобождает все автоматические запрошенные буфера , после чего закрывает поток . Из библиотеки textbackground() - с помощью этой функции устанавливается цвет фона для функции cprintf(). textcolor() - с помощью этой функции устанавливается цвет текста для функции cprintf(). clrscr() - функция очистки экрана, цветом установленным функцией textbackground(). cprintf() - с помощью этой функции осуществляется вывод строки с учетом цветов установленных функциями textbackground(), textcolor(). Данных режимов в Си всего три - NOCURSOR (курсор выключен), SOLIDCURSOR (курсор в виде сплошного блока) NORMALCURSOR (обычный курсор). getch() - функция getch осуществляет считывание первого единственного символа с клавиатуры, используется при считывании клавиш курсора при перемещении по окну выбора режима работы программы. gotoxy() - эта функция перемещает курсор в нужную часть экрана, обычно используется перед функцией cprintf().Данная программа предназначена для анализа методов сортировки массивов быстрой и слиянием . Программа может работать на 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. Программа не требует от пользоватля ввода массива для его сортировки. А так как в программе используется секундомер, то тактовая частота компьютора, на котором демонстрируется программа, влияет на точность выводимых результатов.Путем незначительных изменений в программе, можно приспособить программу специально для сортировки массивов. Данная программа (test.exe) является единым исполняемым модулем и не требует наличия любых других установленных программных средств. После загрузки программы оператору будет предл

СОДЕРЖАНИЕ

Введение 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