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

Так же программа  содержит стандартные функции языка  Си, описанные в библиотеках: <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 в виде unsigned char или 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) и суммированием 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()

Быстрая сортировка состоит в том , что список В=<k1,k2,…,kn> реорганизуется в B',<k1>,B”,где В' - подсписок В с элементами , не большими k1 , а B” - подсписок В с элементами большими k1. В списке В',<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() вызывается везде, где появляется ошибка.(создает окно сообщения). В случае необходимости программу можно остановить в любом месте её исполнения следующими комбинациями клавиш: Ctrl C или Alt X.

Вызов программы осуществляется путём запуска  файла test.exe, при этом программа будет  работать в интерактивном  режиме.

Окно помощи программы содержит: название программы, данные о разработчике, назначение, функциональные клавиши используемые в программе, и возможные проблемы при ее выполнении.

3.3 РУКОВОДСТВО  ОПЕРАТОРА

Основной  функцией данной программы  является определение  времени сортировки массивов методами быстрой  и слиянием. Путем  незначительных изменений  в программе, можно  приспособить программу  специально для сортировки массивов. Данная программа (test.exe) является единым исполняемым  модулем и не требует  наличия любых  других установленных  программных средств. Она так же не требует  установки на компьютер, каких бы то ни было специфических аппаратных средств.

Контрольный пример выполнения программы  приведён в приложении 2.

Программа может работать лишь в интерактивном  режиме. Сортировка массива с большим  числом элементом  на современном компьютере займет всего несколько  секунд и зависит  от размера сортируемого массива.

После загрузки программы  оператору будет  предложено нажать необходимую  клавишу для продолжения  выполнения программы , для вывода информации о программе или для выхода. Если программа не содержит файла text.hlp или не найдан драйвер EGAVGA.BGI, то программа выдаёт окно сообщения об ошибке. Если программа содержит все необходимые элементы, то она выдаст окно сообщния о возможности выполнения анализа сортировки. Если программа получила разрешение на начало процесса сортировки, то она выполняет его и после завершения выводит на экран в графическом режиме результаты о анализе сортировок. В случае необходимости программу можно остановить в любом месте её исполнения следующими комбинациями клавиш: Ctrl C или Alt X. В таком случае программа не выполнит ни каких действий.

Окно помощи программы содержит: название программы, данные о разработчике, назначение, функциональные клавиши используемые в программе, и возможные проблемы при ее выполнении.

 

ЗАКЛЮЧЕНИЕ

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

 

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Шолмов Л.И. Руководство по турбо Си. М.: Наука, 1994. - 94-98с.

Уинер Р. Язык Турбо Си : Пер. с англ. -М.:: Мир, 1991. - 384 с.

Керниган Б.В, Ричи Д.М. Си для профессионалов. М.: Энергия, 1996.- 213 с.

Грейд Дж. Математическое программирование. М.: Наука, 1987. - 241 с.

Либерман М. Алгоритмы сортировки массивов. М.: Наука, 1997. - 43-81с.

 

Приложение 1

ЛИСТИНГ ПРОГРАММЫ