Отчет (Реализация алгоритма сортировки для АТД)

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

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

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

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

ВЫПОЛНИЛ:

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

Васильев О.М.

ПРОВЕРИЛ:

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

Филатов В.В.

Москва 2012г.

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

Решение:

1. Листинг программы с програмным подсчетом операций:

<main.cpp>

#include "header.h"

int find_max(CTEK *Stack1, int *Nop){ // 21 + Сумма(19) + Сумма(18)

CTEK temp; //+1 *Nop = *Nop + 1;

int Value,Maximum; //+2 *Nop = *Nop + 1;

Maximum = Stack1->GetValue(); //10 *Nop = *Nop + 10;

temp.PutValue(Maximum); //+7 *Nop = *Nop + 7;

while(!Stack1->IsEmpty()){ //СУММА(19) *Nop = *Nop + 1;

Value = Stack1->GetValue();//+10 *Nop = *Nop + 10;

if(Maximum < Value){ //+1 *Nop = *Nop + 1;

Maximum = Value; //+1 *Nop = *Nop + 1;

}

temp.PutValue(Value); //+7 *Nop = *Nop + 7;

}

while(!temp.IsEmpty()){ //СУММА(18) *Nop = *Nop + 1;

Stack1->PutValue(temp.GetValue());//+18 *Nop = *Nop + 18;

} *Nop = *Nop + 1;

return Maximum; //+1

}

//6 + Сумма(18) + Сумма(34 + Сумма(18)+Сумма(18))

CTEK* Koll_povtor(CTEK *Stack1, CTEK *Stack2, int *Nop){

CTEK temp1,temp2; //+2 *Nop = *Nop + 2;

int Value1,Value2,i,j; //+4 *Nop = *Nop + 4;

while(!Stack1->IsEmpty()){//Сумма(34+Сумма(18)_+ Сумма(18)) *Nop = *Nop + 1;

Value1 = Stack1->GetValue();//+10 *Nop = *Nop + 10;

temp1.PutValue(Value1); //+7 *Nop = *Nop + 7;

for(i=0;i<Value1;i++){ //Сумма(18) *Nop = *Nop + 1;

temp2.PutValue(Stack2->GetValue());*Nop = *Nop + 18;

}

Value2 = temp2.GetValue() + 1; //+10 *Nop = *Nop + 10;

Stack2->PutValue(Value2); //+7 *Nop = *Nop + 7;

for(i=1;i<Value1;i++){ //Сумма(18) *Nop = *Nop + 1;

Stack2->PutValue(temp2.GetValue()); *Nop = *Nop + 18;

}

}

while(!temp1.IsEmpty()){ //Сумма(18) *Nop = *Nop + 1;

Stack1->PutValue(temp1.GetValue()); *Nop = *Nop + 18;

} *Nop = *Nop + 1;

return Stack2; //+1

}

// 2 + Сумма(17)+Сумма(18)

CTEK* summirovanie(CTEK *Stack, int *Nop){

CTEK temp; //+1 *Nop = *Nop + 1;

int Sum=0; //+1 *Nop = *Nop + 1;

while(!Stack->IsEmpty()){ //Сумма(17 *Nop = *Nop + 1;

Sum = Sum + Stack->GetValue();//+10 *Nop = *Nop + 10;

temp.PutValue(Sum); //+7 *Nop = *Nop + 7;

}

while(!temp.IsEmpty()){//Сумма(18) *Nop = *Nop + 1;

Stack->PutValue(temp.GetValue());//+18 *Nop = *Nop + 18;

} *Nop = *Nop + 1;

return Stack; //+1

}

//9 + Сумма(21) + Сумма(18)

CTEK* sortirovka(CTEK *Stack, int *Nop){

CTEK temp;//+1 *Nop = *Nop + 1;

int i,j,k,Value; //+4 *Nop = *Nop + 4;

j = 0;k = 0;i = 999;//+3 *Nop = *Nop + 3;

while(!Stack->IsEmpty()){//Сумма(21) *Nop = *Nop + 1;

k = k + 1; //+2 *Nop = *Nop + 2;

Value = Stack->GetValue(); //+10 *Nop = *Nop + 10;

if(i != Value){ //+1 *Nop = *Nop + 1;

i = Value; //+1 *Nop = *Nop + 1;

for(j=j;j<i;j++){ //+7 *Nop = *Nop + 1;

temp.PutValue(k); *Nop = *Nop + 7;

}

}

}

while(!temp.IsEmpty()){ //Сумма(18) *Nop = *Nop + 1;

Stack->PutValue(temp.GetValue());//+18 *Nop = *Nop + 18;

} *Nop = *Nop + 1;

return Stack;//+1

}

void main(int k){

setlocale(LC_CTYPE, "");

int size, max, val, Nop, N, T;

for(int i=0; i<=9; i++){

Nop = 0;

double T = GetTickCount();//+2 Nop += 2;

cout<<"__________________________" << endl; //+2

Nop += 2;

size = 100 * (i+1); //+1 Nop ++;

cout<<"Размер стека: "<< size << endl; //+3 Nop += 3;

CTEK Stack1, Stack2; //+2 Nop += 2;

for (int i=0; i<size; i++){ Сумма(8) Nop ++;

val = 100 + rand()%900;//+1 Nop ++;

Stack1.PutValue(val); //+18 Nop += 7;

}

max = find_max(&Stack1, &Nop);

for(int i=0; i<max; i++){ //Сумма(7) Nop ++;

Stack2.PutValue(0); //+7 Nop += 7;

}

Stack2 = *Koll_povtor(&Stack1, &Stack2, &Nop);

Stack2 = *summirovanie(&Stack2, &Nop);

Stack2 = *sortirovka(&Stack2, &Nop);

соut << "Количество операций = " << Nop + 3 << endl; //+3

cout << "Затраченное время = " << (T - GetTickCount())*(-1)/1000 << " сек." << endl;

}

}

2. Расчет трудоемкости:

O(F(n))=36*n*n

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

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

4. Контрольный пример (принтскрин значений N, t, Nop):