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

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

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

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]<v[left])swap(v,++last,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<l1;i++) *pa++=w[i];

for(i=l1;i<l2;i++) *pb++=w[i];

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

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

for(i=0;i<l2;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.