Время работы алгоритма t примерно оценивается формулой:t=a*NЅ + b*N*logN
где a,b - неизвестные константы, зависящие от программной реализации алгоритма.
Сортировка посредством слияния
Алгоритмы сортировки этого класса основываются на объединении нескольких (часто двух) уже упорядоченнх файлов. Рассмотренные далее алгоритмы выбирают из исходного файла упорядоченные отрезки и объединяют их в более длинные.
Естественное двухпутевое слияние
Этот алгоритм ищет упорядоченные отрезки с двух концов файла ипереписывает их по очереди также в оба конца. Повторяя эту процедуру в цикле, мы приходим к середине файла, что означает окончание сортировки.
Элементы файла пересылаются из одной области в другую, меняя направление пересылки. Для запоминания направления пересылки служит переменная s, принимающая значения TRUE и FALSE попеременно. Другой логический признак f служит сигналом продолжения-окончания алгоритма, если все области слились в конце концов в одну. Переменная d принимает попеременно значения +1 -1 и указывает направление просмотра файла: вперед или назад.Операция <-> обозначает обмен значениями двух переменных. Операция Џ обозначает инверсию логической переменной или выражения.
Время работы алгоритма t примерно оценивается формулой:
t=a*N*lgN + b*N
Простое двухпутевое слияние.
В алгоритме естественного двухпутевого слияния упорядоченный отрезки файла определялись случайным расположением элементов в исходном файле. В данном алгоритме длина отрезков фиксируется на каждом шаге. В исходной файле все отрезки имеют длину 1, после первого шага она равна 2, после второго 4, после третьего - 8, после к-го шага -2 в степени к.
Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N
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-DOS 3.0 и выше.
Программа содержит пять основных функций: main(), file(), 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.
Страницы: 1, 2, 3, 4, 5
