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

. 3. РАЗРАБОТКА ПРОГРАММЫ

3.1 ОПИСАНИЕ ПРОГРАММЫ

Данная программа называется “TEST” (имя исполняемого файла test.exe) и предназначена для анализа методов сортировки одномерного массива. Программа работает на IBM совместимых компьютерах семейства х86 начиная с 286 и выше, в операционной системе типа Ms-DOS 3.0 и выше.

Программа содержит пять основных функций: main(), fi

le(), qsort(), srecmg(), grafix(). Все переменные, используемые в программе являются локальными.

Функция main() содержит пункты меню и вызывает другие исполняемые функции в зависимости от нажатия предложеных функциональных клавиш F1, F2 и F10. Каждая из этих функций работает автономно и независимо от двух других.

Программа реализована как в псевдографическом так и в графическом режиме (в связи с чем она может компилироваться только в DOSовских версиях BorlandC++ или BorlandC). В графическом режиме она выводит на экран гистограмму которая характеризует время сортировки массивов двумя способами.

Программа использует как стандартный так и файловый ввод-вывод информации . Стандартный ввод представлен запросом программы на ввод функциональных клавиш , которые задают характер выполняемого действия . Файловый ввод-вывод используется в функции 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 в виде 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 уже находится на месте где он должен быть в отсортированом списке. Дальше к спискам В’ и В’’ применяется упорядованичение быстрой сортировкой .

 Скачать реферат