Структуры и алгоритмы обработки данных

МОСКВОСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

КУРСОВАЯ РАБОТА

по дисциплине: «Структуры и алгоритмы обработки данных»

на тему: «Реализация алгоритма сортировки для АТД»

ВЫПОЛНИЛ:

Студент 2-го курса гр ИТ-6

Кульнев А.М.

ПРОВЕРИЛ:

Доцент кафедры ИТ-6

Филатов В.В.

г.Москва 2011г.

Задание: Написать программу, реализующую алгоритм сортировки естественным двухпутевым слиянием для АТД «Стек» и определить его трудоёмкость.

Решение:

1. Листинг с теоретическим расчётом трудоёмкости:

<main.cpp>

#include "headers.h"

enum {MAX_AVERAGE_COUNT=1, MAX_POWER=12};

int STACK_SIZE = 512;

double Nop=0;

void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length);

void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2);

void main(){

setlocale(LC_CTYPE, "");

cout.setf(ios::fixed);

for(int power=0; power < MAX_POWER; power++){

DWORD tick_start = GetTickCount();

Nop = 0;

for(int average_count=0; average_count<MAX_AVERAGE_COUNT; average_count++){

MyStack Stack1, Stack2;

srand(time(0));

for(int i=0; i<STACK_SIZE; i++)

Stack1.PutValue(100+rand()%900);

int natural_length=0;

while(natural_length!=STACK_SIZE){

natural_length=0;

MyStack natural_stack_1, natural_stack_2;

stack_get_natural(Stack1, natural_stack_1, natural_length);

stack_get_natural(Stack1, natural_stack_2, natural_length);

stack_merge(Stack2, natural_stack_1, natural_stack_2);

if (Stack1.IsEmpty()){

Stack1 = Stack2;

MyStack tmp;

Stack2 = tmp;

}

}

}

int tick_average = (GetTickCount()-tick_start)/MAX_AVERAGE_COUNT;

cout << "----------" << endl;

cout << " N = " << STACK_SIZE << endl;

cout << " t = " << tick_average <<endl;

cout << " Nop = " << Nop/MAX_AVERAGE_COUNT << endl;

cout << "----------" << endl;

STACK_SIZE *= 2;

}

system("pause");

}

void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length){

if (Stack.IsEmpty())

return;

natural_length++;

new_stack.PutValue(Stack.GetValue());

while(!(Stack.IsEmpty()|| Stack.Value() > new_stack.Value())){

natural_length++;

new_stack.PutValue(Stack.GetValue());

}

}

void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2){

while(true){ if (nat_stack_1.IsEmpty()) {

while(!nat_stack_2.IsEmpty()){

result_stack.PutValue(nat_stack_2.GetValue());

break;

} else if (nat_stack_2.IsEmpty()){

while(!nat_stack_1.IsEmpty()){

result_stack.PutValue(nat_stack_1.GetValue());

break;

} else { if (nat_stack_2.Value() <= nat_stack_1.Value())

result_stack.PutValue(nat_stack_2.GetValue());

else

result_stack.PutValue(nat_stack_1.GetValue());

}

}

}

2. Листинг с инкрементами, повторяющими теоретический расчёт:

<main.cpp>

#include "headers.h"

enum {MAX_AVERAGE_COUNT=1, MAX_POWER=12};

int STACK_SIZE = 512;

double Nop=0;

void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length);

void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2);

void main(){

setlocale(LC_CTYPE, "");

cout.setf(ios::fixed);

for(int power=0; power < MAX_POWER; power++){

DWORD tick_start = GetTickCount();

Nop=0;

for(int average_count=0; average_count<MAX_AVERAGE_COUNT; average_count++){

MyStack Stack1, Stack2; Nop+=2;

srand(time(0)); Nop+=2;

Nop+=3;

for(int i=0; i<STACK_SIZE; i++){ Nop++;

Stack1.PutValue(100+rand()%900); Nop+=13;}

int natural_length=0; Nop+=2;

Nop++;

while(natural_length!=STACK_SIZE){ Nop++;

natural_length=0; Nop++;

MyStack natural_stack_1, natural_stack_2; Nop+=2;

stack_get_natural(Stack1, natural_stack_1, natural_length); Nop++;

stack_get_natural(Stack1, natural_stack_2, natural_length); Nop++;

stack_merge(Stack2, natural_stack_1, natural_stack_2); Nop++;

Nop+=3;

if (Stack1.IsEmpty()){ Nop+=3;

Stack1 = Stack2; Nop+=4;

MyStack tmp; Nop++;

Stack2 = tmp; Nop++;

}

}

}

int tick_average = (GetTickCount()-tick_start)/MAX_AVERAGE_COUNT;

cout << "----------" << endl;

cout << " N = " << STACK_SIZE << endl;

cout << " t = " << tick_average / MAX_AVERAGE_COUNT << endl;

cout << " Nop = " << Nop/MAX_AVERAGE_COUNT << endl;

cout << "----------" << endl;

STACK_SIZE *= 2;

}

system("pause");

}

void stack_get_natural(MyStack& Stack, MyStack& new_stack, int& natural_length){

if (Stack.IsEmpty()){ Nop+=3;

Nop++;

return;}

natural_length++; Nop++;

new_stack.PutValue(Stack.GetValue()); Nop+=19;

Nop+=11;

while(!(Stack.IsEmpty()|| Stack.Value() > new_stack.Value())){ Nop+=11;

natural_length++; Nop++;

new_stack.PutValue(Stack.GetValue()); Nop+=19;

}

}

void stack_merge(MyStack& result_stack, MyStack& nat_stack_1, MyStack& nat_stack_2){

Nop++;

while(true){ Nop++;

if (nat_stack_1.IsEmpty()) { Nop+=3;

Nop+=3;

while(!nat_stack_2.IsEmpty()){ Nop+=3;

result_stack.PutValue(nat_stack_2.GetValue()); Nop+=19;}

Nop++;

break;

} else if (nat_stack_2.IsEmpty()){ Nop+=4;

Nop+=3;

while(!nat_stack_1.IsEmpty()){ Nop+=3;

result_stack.PutValue(nat_stack_1.GetValue()); Nop+=19;}

Nop++;

break;

} else { Nop++;

if (nat_stack_2.Value() <= nat_stack_1.Value()){ Nop+=7;

result_stack.PutValue(nat_stack_2.GetValue()); Nop+=19;}

else{ Nop++;

result_stack.PutValue(nat_stack_1.GetValue()); Nop+=19;}

}

}

}

3. Таблица и графики:

С1 = С2 = С3 = С4 =