Расчётно-графическая работа 2002

Новосибирский государственный технический университет

Кафедра вычислительной техники

Расчётно-графическая работа 2002

Вариант №13

Вариант: 13

Группа: АМ-215

Бригада: 5

Студенты:

Новосибирск 2002

1.  Постановка задачи:

13.“Быстрая” сортировка разделением с подсветкой разделяемой части и элемента-медианы.

2.  Неформальное описание основных идей алгоритма.

РГР выполнен как программа в Борланд СИ. Заданный массив сортруется разделением. Считается среднее арифметическое элементов массива в заданных границах, это и будет медиана. После этого вызывается функция сортировки, элементы большие медианы переписываются в первый вспомогательный массив, а элементы меньшие медианы во второй вспомогательный массив. Затем элементы из первого и второго вспомогательных массивов переписываются обратно в сортируемый массив. После этого опять вызывается функция сортировки для кождойгрупы чисел, которые разбивались. Разделения происходят пока массив не отсортируется.

На экране это выглядит так: появляется сортируемый массив, подсвечиваются элементы большие медианы синим цветом, а элементы меньшие медианы зеленым цветом. После этого элементы большие медианы перебигают в 1 вспомогательный массив, а элементы меньшие медианы во 2 вспомогательный массив. Затем элементы из обоих вспомогательных массивов перебигают обратно в сортируемый массив.

3.  Описание структур данных используемых в программе.

4.  Описание основных идей алгоритма с использованием управляющих конструкций языка СИ и текстовых формулировок результата выполнения.

Функции:

Sort ( ) – функция сортировки массива, сортировка происходит методом разбиения массива.

Stroka ( ) – функция которая делает заставку. Заставка представляет собой выпадение символов заданного текста сверху экрана до заданных координат (координаты задаются).

Move ( ) – функция которая перемещает число из заданных координат в другие заданные координаты.

Esc ( ) – функция выхода из программы. После того как был нажат Esc она запрашивает подтверждения.

5.  Текст программы с комментариями на все структуры данных, заголовки функций и принципиальные фрагменты алгоритмов.

#include<conio. h>

#include<string. h>

#include<stdlib. h>

#include<dos. h>

#include<stdio. h>

#include<alloc. h>

extern int d=0;

void Stroka(char str[]) //функция заставки

{

char stroka[]="lalala", *ck;

int y, sx=17,sy=10,cs, sout=0;

clrscr ();randomize ();

ck=new char [strlen(str)];

for (y=0; y<strlen(str); y++) //заполнение массива "-" - ами

*(ck+y)='-';

while (sout<strlen (str))

{cs=random (strlen(str)); //определение еще не выведенной буквы

while (*(ck+cs)!='-')

cs=random (strlen(str));

*(ck+cs)='v'; // Чтобы элементы не повторялись

sout++; // вместо использованных элементов ставим "птички"

for (y=1; y<sy; y++)

{textcolor (9); // задаем цвит

gotoxy (sx+cs, y); //написание текста ниже

cprintf ("%c", str[cs]);

gotoxy (sx+cs, y-1); //затирание стaрого текста

printf (" ");

delay (10); // здесь ставим скорость падения букв

}}}

void step(int v, int &x, int &y, int r)

{

gotoxy(x, y);

cprintf(" ");

if (abs(r)>1) y+=r/2;

else x+=r;

gotoxy(x, y);

cprintf("%2d",v);

delay(10);

}

void move(int x0,int y0,int x1,int y1,int v) //функция перемещения символов

{

int dx=x1>x0 ? 1 :-1;

int dy=y1>y0 ? 1 :-1;

int y2=(y0+y1)/2;

while (y0!=y2) step(v, x0,y0,dy*2);

while (x0!=x1) step(v, x0,y0,dx);

while(y0!=y1) step(v, x0,y0,dy*2);

}

void sort (int in [],int a, int b) //функция сортировки заданного массива

{

int v1[20]; //первый вспомогательный массив

int v2[20]; //второй вспомогательный массив

if (a>=b) return;//проверка на правильность границ

int h, f,k, l,i, j;int w=0;int z=0;

double t=0; //инициалтзируем медиану

for (h=a, b;h<=b;h++)

t+=in[h];//считаем медиану

t=t/(b-a+1);

int c=0;

gotoxy(25,13);//перемещаем курсор в заданную позицию

if (a>0)

for(;c<a;c++){textcolor(7); cprintf("%d ",in[c]);}//выводит неиспользуемые элементы

for (int s=a;s<=b;s++)//цикл подсвечивает элементы

if (in[s]>=t)

{textcolor(9);cprintf("%d ",in[s]);}//большие медианы синим цветом

else {textcolor(2);cprintf("%d ",in[s]);}//меньшие медианы зеленым цветом

if(b<10)

for(int q=b+1;q<10;q++)

{textcolor(7);cprintf ("%d ",in[q]);} //выводит оставшиеся элементы

d++;

gotoxy(25,18);textcolor(4);

cprintf("Медиана равна:");//печатает текст в заданной позиции, заданным цветом

cprintf(" %f",t);

gotoxy(25,20);textcolor(3);cprintf("Количество разделений:");cprintf(" %d",d);

for(int h1=a;h1<=b;h1++)

if(in[h1]>=t)//переносит элементы большие медианы в вспомогательный массив

{textcolor(9);move(25+2*h1,13,24+2*w,16,in[h1]);w++;};

for(h1=a;h1<=b;h1++)

if(in[h1]<t) //переносит элементы меньшие медианы в вспомогательный массив

{textcolor(2);move(25+2*h1,13,24+2*z,15,in[h1]);z++;};

delay(50);

for (h=a, k=0,l=0;h<=b;h++)//записывает элементы меньшие медианы в

if (in[h]>=t) //вспомогательный массив v1, а элементы большие

v2[l++]=in[h]; //медианы в массив v2

else

v1[k++]=in[h];

if (k==0) return;

for(w=0,h1=a;w<k;w++,h1++)//переносит элементы меньшие медианы из вспомогательного

{textcolor(2); move(24+2*w,15,24+2*h1,13,v1[w]);}//массива в исходный

for(z=0;z<l;z++,h1++)//переносит элементы меньшие медианы из вспомогательного

{textcolor(9); move(24+2*z,16,24+2*h1,13,v2[z]);}//массива в исходный

for (h=a, j=0;j<k;h++,j++)//записывает элементы обратно в сортируемый массив

in[h]=v1[j];

i=h;

for (j=0;j<l;h++,j++)//записывает элементы обратно в сортируемый массив

in[h]=v2[j];

sort(in, a,i-1);//вызывается функция сортировки для границ от первой границы до медианы

sort(in, i,b);//вызывается функция сортировки для границ от медианы до второй границы

}

int Esc()//функция выхода из программы

{

char value;

cprintf("Вы увеpенны?");//запрашивает подтверждение

value=getch();

if(value=='Y'||value=='y')return 1;

return NULL;

}

void main()//функция main

{ while(1)

{

clrscr();

_setcursortype(0);//выполняет затирание курсора

char text1[]="AM-215 PROGRAMMING TECNOLOGIES PRESENTS...";//задается строка которая используется, как заставка

Stroka(text1);//вызов функции заставки

gotoxy(20,10);textcolor(5);

cprintf("\n1 - Начать сортировку");

gotoxy(20,12);textcolor(2);cprintf("\n2 - О программе");

gotoxy(20,14);textcolor(RED);cprintf("\nESC - Выход");

switch(getch())

{

case '1':

{ d=0;//обнуляется количество перестановок

clrscr();int B[10]={9,1,8,2,7,3,6,4,5,0};int a; int b;//задается сортируемый массив

gotoxy(37,2);textcolor(3);cprintf("Введите гранцы сортировки :");

gotoxy(37,3);textcolor(3);cprintf("Первая граница: ");cscanf("%d",&a);//запрашиваются границы

gotoxy(37,4);textcolor(3);cprintf("Вторая граница: ");cscanf("%d",&b);//запрашиваются границы

gotoxy(10,8);textcolor(6);

if(a>=10)break;if(a>=10)break;//проверяются границы на размерность заданного массива

cprintf ("Исходный массив: ");

for (int r=0;r<10;r++) cprintf(" %d",B[r]);

gotoxy(3,2);textcolor(7);cprintf("* - не используемые элементы");

gotoxy(3,3);textcolor(9);cprintf("* - элементы большие медианы");

gotoxy(3,4);textcolor(2);cprintf("* - элементы меньшие медианы");

gotoxy(1,14);textcolor(2);cprintf("\nВспомогательный массив: "); // 24

gotoxy(1,15);textcolor(9);cprintf("\nВспомогательный массив: ");

sort(B, a,b);//вызывается функция сортировки

gotoxy(20,22);textcolor(6);cprintf("Отсортированный массив:");

for(int y=0;y<10;y++)cprintf(" %d",B[y]);

getch();getch();

break;

}

case '2'://если нажать'2'появляются сведения о программе

{

clrscr();gotoxy(1,10);textcolor(2);//задается положение и цвет текста

cprintf("Программа разработана Ракальевым Василием, для того ");

cprintf("чтобы наглядно показать выполнение комьютером сортировки ");

cprintf("методом разделения. Несанкционированное распространение ");

cprintf("запрещено и преследуется по закону! Все права принадлежат");

cprintf(" Ракальеву Василию Александровичу.");getch();break;

}

case 27 ://если нажать Esc вызывается функция выхода из программы

{ textcolor(RED);gotoxy(20,23);if(Esc())return;break;}

}

}

}