Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

Приложение 1

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

// листинг программы сортировки массивов разработанная Андрусевичем Б.И.

#include

#include

#include

#include

#include

#include

#include

//--------------------------

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(" Эта программа демонстрирует сортировку массива двумя методами:");

window(2, 3, 79, 3);

puts(" быстрым методом и методом слияния. После чего определяется время сор-");

window(2, 4, 79, 4);

puts(" тировки массива каждым методом и результат выводится в виде гисто-");

window(2, 5, 79, 5);

puts(" граммы.");

window(2, 6, 79, 6);

window(20, 10, 60, 15);

textcolor(WHITE);

textbackground(LIGHTGRAY);

cprintf("+------------------------------------------------------------------+");

cprintf("¦ НЕОБХОДИМЫЕ ФАЙЛЫ ПРИСУТСТВУЮТ ¦");

cprintf("¦ (для тестировния нажмите F2) ¦");

cprintf("+------------------------------------------------------------------+");

closegraph();

}

}

//-----------------------

void Error()

{

window(20, 10, 60, 15);

textcolor(WHITE);

textbackground(LIGHTGRAY);

cprintf("+----------------- Ошибка ----------------+");

cprintf("¦ ¦ ");

cprintf("¦ ¦");

cprintf("¦ ¦");

cprintf("+---------------------------------------------+");

}

//-------------< Функция помощи >----------------

help()

{

int n = 1;

FILE *hl; // Указатели на файл

char string[78];

if ((hl = fopen("test.hlp", "r")) != NULL) // Проверка на открытие файла

{

windows(0);

window(2, 2, 78, 23);

textcolor(BLACK);

while (fgets(string, 78, hl) != NULL && n < 23)

{

gotoxy(1, n++); // Построчный вывод файла

cputs(string); // помощи

}

window(36, 1, 44, 1);

printf(" Помощь "); // Вывод заголовка помощи

while (27 != getch());

}

else{

Error();

window(29, 12, 52, 12);

textcolor(BLACK);

cprintf("Файл TEST.HLP не найден");

getch();

windows(1);

}

fclose(hl);

windows(1);

return 0;

}

//--------< Функция построения гистограмм>-------

grafix(double simvol[2])

{

double CopySimvol[2]; // Масив количества символов

long float max = 0;

int gdriver = DETECT, gmode, errorcode;

int midx = 50; // Обявление переменных

int midy = 410; // с заданними начальными

int i, s; // значениями

int siz = 100;

int otst = 10;

int rovn = 45;

char chis[2];

char buf[10];

initgraph(&gdriver, &gmode, "");

errorcode = graphresult(); // Запись код ошибки

if (errorcode != grOk) // Проверка на ошибку

{

Error(); // Вызов функции окна

window(26, 12, 54, 12);

textcolor(BLACK);

cprintf("Драйвер EGAVGA.BGI не найден");

getch();

windows(1);

return 0;

}

for (int y = 0; y < 2; y++) // Оприделение максимального

if (max < simvol[y]) // числа

max = simvol[y];

for (int b = 0; b < 2; b++) // Оприделение высоты столбцов

CopySimvol[b] = simvol[b] * 200 / max;

setfillstyle(CLOSE_DOT_FILL,9);

for (int n = 0; n < 2; n++) // Построение столбцов и линий

{

setcolor(BLUE);

bar3d(midx + otst + siz * n, midy - CopySimvol[n], midx + siz* (n+1 ), midy, 15, 1);

setcolor(BROWN);

line(midx + rovn + siz * n, midy + otst, midx + rovn + siz * n, midy + otst * 2);

sprintf(chis, "%d", n + 1);

setcolor(GREEN);

outtextxy((midx + rovn + siz * n) - 2, midy + otst * 2, chis);

setcolor(CYAN);

sprintf(buf, "%lf", simvol[n]);

outtextxy((midx + rovn + siz * n) - 15, midy - CopySimvol[n] - rovn, buf);

}

setcolor(BROWN);

line(midx, 100, midx, midy + otst); // Построение оси Y

line(midx, midy + otst, 280, midy + otst); // Построение оси X

line(midx - otst, midy - 200, midx, midy - 200); // Построение

line(midx - otst, midy - 100, midx, midy - 100); // линии

settextstyle(DEFAULT_FONT, HORIZ_DIR, 1);

setcolor(GREEN);

outtextxy(535, 460, "ESC ");

outtextxy(10, 205, "100");

outtextxy(10, 305, "50");

outtextxy(350, 235, "1. Сортирвка массива быстрым");

outtextxy(350, 250, " методом");

outtextxy(350, 280, "2. Сортирвка массива методом");

outtextxy(350, 295, " слияния");

setcolor(LIGHTBLUE);

outtextxy(300, 423, "метод");

outtextxy(570, 460, "Выход");

settextstyle(DEFAULT_FONT, HORIZ_DIR, 2);

outtextxy(220, 30, "ГИСТОГРАММА ");

settextstyle(DEFAULT_FONT, VERT_DIR, 1);

outtextxy(48, 160, "время");

while (27 != getch()); // Проверка на символ ESC

closegraph();

windows(1);

return 0;

}

/*qsort:сортирует v[left]...v[right] по возрастанию*/

void qqsort( int v[], int left, int right)

{

int i,last;

delay(1);

void swap( int v[], int i, int j);

if(left>=right) /*ничего не делается если*/

return; /* в массиве менее двух эл-тов */

swap(v,left,(left+right)/2); /*делящий эл-нт переносится в v[0]*/

last=left;

for(i=left+1;i<=right;i++) /*деление на части*/

if(v[i]

swap(v,left,last); /*перезапоминается делящий элемент*/

qqsort(v,left,last-1);

qqsort(v,last+1,right);

}

void swap( int v[], int i, int j)

{

long int temp;

temp=v[i];

v[i]=v[j];

v[j]=temp;

}

/*SRECMG -- РЕКУРСИВНАЯ СОРТИРОВКА СЛИЯНИЕМ*/

void srecmg(a,n)

int a[],n;

{

void merge( int*, int, int);

int i;

delay(1);

if(n>1)

{i=n/2;srecmg(a,i);srecmg(a+i,n-i);merge(a,i,n);}

}

/*merge--слияние двух подсписков*/

#define MAX(x,y) ((y)<(x)?(x):(y))

void merge( int*w, int l1, int l2)

{

int*a,*pa,*pb,i;

a=( int*)calloc(l2+2,sizeof( int));

pa=a;pb=a+l1+1;

for(i=0;i

for(i=l1;i

*pa=*pb=MAX(w[l1-1],w[l2-1])+1;

pa=a;pb=a+l1+1;

for(i=0;i

w[i]=(*pa<*pb?*pa++:*pb++);

free(a);

}

#define ww 700

//--------------

file()

{ void qqsort( int *, int,int);

void srecmg( int*, int);

double simvol[2];

int s;

clock_t start,start2,end,end2; int t=0;

int gener1[ww],gener2[ww]; //Генератор случайных чисел

randomize(); //Устанавливает генератор в 0

for ( s=0 ; s < ww ; s++)

{ gener1[s]= ( rand()%100 ); // rand()-функция генератора

gener2[s] =gener1[s];

}

{ start=clock();

qqsort(gener1,0,ww-1);

end=clock();

simvol[0] = ((end - start)/CLK_TCK);

}

{ start2 =clock();

srecmg(gener2,ww);

end2=clock();

simvol[1] = ((end2 - start2)/CLK_TCK);

}

grafix(simvol); // Вызов функции построения гистограмм

windows(1);

return 0;

}

//-------------------< Меню >--------------------

void main()

{

char press;

windows(1);

while (1)

{

press = getch(); // Опрос клавиатуры

switch(press)

{

case 59: help(); break; // Вызов помоши

case 60: file(); break; // Запуск гистограммы

case 68: { // Выход из программы

window(1, 1, 80, 25);

textbackground(BLACK);

clrscr();

exit(1);

} } }}

Приложение 2

КОНТРОЛЬНЫЙ ПРИМЕР ВЫПОЛНЕНИЯ ПРОГРАММЫ

В качестве примера возьмём исходный файл “Test.exe” и запустим его . На экране появляется окно собщения о наличии необходимых файлов. Для продолжения выполнения программы пользователь нажимает клавишу F2 , в результате чего на экране появляется гистограмма , характеризующая скорость выполнения сортировки массивов. Воспользовавшись клавишей Esc , пользователь выходит с графического режима в режим отображения меню. При нажатии пользователем клавиши F1 на экране появляется окно помощи которое содержит название программы, данные о разработчике, назначение, функциональные клавиши используемые в программе, и возможные проблемы при ее выполнении.Нажатие клавиши Esc приводит к закрытию окна помощи. Для выхода из программы пользователь должен нажать клавишу F10.

П ример выводимой гистограммы.

Характеристики

Список файлов курсовой работы