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’’ приблизительно одинаковой длины ; тогда необходимо (nlog2 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 РУКОВОДСТВО ПРОГРАММИСТА
Вызов программы осуществляется путём запуска файла test.exe, при этом программа будет работать в интерактивном режиме.
Окно помощи программы содержит: название программы, данные о разработчике, назначение, функциональные клавиши используемые в программе, и возможные проблемы при ее выполнении.
3.3 РУКОВОДСТВО ОПЕРАТОРА
Окно помощи программы содержит: название программы, данные о разработчике, назначение, функциональные клавиши используемые в программе, и возможные проблемы при ее выполнении.
ЗАКЛЮЧЕНИЕ
В результате выполнения курсового проекта была написана программа, анализирующая сортировку массивов способами быстрой и слиянием. Программа обладает высоким параметром быстродействия, маленьким размером и не требовательна к системным ресурсам компьютера. В качестве недостатка программы можно отнести то, что точность выполнения программы зависит от тактовой частоты компьютера. Этот недостаток можно решить путём изменения количества сортируемых элементов массива. Программа может быть преобразована для использования в целях сортировки массивов вводимых пользователем.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Шолмов Л.И. Руководство по турбо Си. М.: Наука, 1994. – 94-98с.
2. Уинер Р. Язык Турбо Си : Пер. с англ. -М.:: Мир, 1991. – 384 с.
3. Керниган Б.В, Ричи Д.М. Си для профессионалов. М.: Энергия, 1996.– 213 с.
4. Грейд Дж. Математическое программирование. М.: Наука, 1987. – 241 с.
5. Либерман М. Алгоритмы сортировки массивов. М.: Наука, 1997. – 43-81с.
Приложение 1
ЛИСТИНГ ПРОГРАММЫ
// листинг программы сортировки массивов разработанная Андрусевичем Б.И.
#include <stdio.h>
#include <dos.h>
#include <graphics.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <time.h>
//-------------< Создание оболочки >-------------
void windows(int w)
{
int n;
_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 < n; k++)
cprintf("¦ ¦");
cprintf("+------------------------------------------------------------------------------+");
if (w == 1)
{
window(2, 2, 79, 2);
puts(" Эта программа демонстрирует сортировку массива двумя методами:");