Инструкция

С О Д Е Р Ж А Н И Е

ВВЕДЕНИЕ. . . 1 Текст программы 2 Описание программы. . 2.1 Общие сведения. 2.2 Функциональное назначение 2.3 Описание логической структуры. . . 2.4 Используемые технические средства 2.5 Вызов и загрузка. 2.6 Входные данные. 2.7 Выходные данные 3 Описание применения. . 3.1 Назначение программы. . . 3.2 Условия применения 3.3 Описание задачи 3.4 Входные и выходные данные 4 Тестовый пример ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ ПРИЛОЖЕНИЕ А Программа сортировки естественным двухпутевым слиянием N_sort.exe

5 6 10 10 10 10 12 12 12 12 13 13 15 13 13 15 16 17

Введение

Обменная сортировка со слиянием оказывается полезной всякий раз, когда мы сталкиваемся с упорядочением массива [1 – 8].

Алгоритм n сортирует записи используя две области памяти, каждая из которых может содержать n записей. Алгоритм простого двухпутевого слияния очень напоминает алгоритм n, тем не менее, методы достаточно отличаются друг от друга.

Время работы алгоритма приблизительно равно 12.5n log2 n, это медленнее быстрой сортировки и не настолько лучше времени работы пирамилальной сортировки (16n log2 n), чтобы оправдать вдвое больший расход памяти.

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

2

2

 

1 Текст программы

#include <iostream>

#include <stdio. h>

#include <math. h>

#include <fstream>

#include <string>

using namespace std;

struct qwerty {

int facktor;

unsigned char name[50];

};

int main() {

int s, d, k, i, j, l, f, n;

cout << "Kol-vo zapicey<<n>>->";

cin >> n;

qwerty qwe[2 * n + 1];

for (int i = 1; i < n + 1; i++) {

cout << "Vvedite factor " << i << "->";

cin >> qwe[i].facktor;

cout << "Vvedite name " << i << "->";

scanf("%s", &qwe[i].name);

qwe[n + i] = qwe[i]; }

3

s = 0;

f = 1;

L2:

if (s == 0) {

i = 1;

j = n;

k = n + 1;

l = 2 * n;

}

if (s == 1) {

i = N + 1;

j = 2 * n;

k = 1;

l = n;

}

d = 1;

f = 1;

L3:

if (qwe[i].facktor > qwe[j].facktor)

goto L8;

if (i == j) {

qwe[k] = qwe[i];

goto L13;

}

qwe[k] = qwe[i];

k = k + d;

i = i + 1;

if (qwe[i - 1].facktor <= qwe[i].facktor)

4

goto L3;

L6:

qwe[k] = qwe[j];

k = k + d;

j--;

if (qwe[j + 1].facktor <= qwe[j].facktor)

goto L6;

else goto L12;

L8:

qwe[k] = qwe[j];

k = k + d;

j--;

if (qwe[i + 1].facktor <= qwe[i].facktor)

goto L3;

L10:

qwe[k] = qwe[i];

k = k + d;

i++;

if (qwe[i - 1].facktor <= qwe[i].facktor)

goto L10;

L12:

f = 0;

d = -1 * d;

swap(k, l);

goto L3;

L13:

if (f == 0) {

s = 1 - s;

5

goto L2;

}

int t, qt;

if (s == 0) {

t = n + 1;

qt = 2 * n ;

} else {

t = 1;

qt = n;

}

cout<<"Stroka posle sortirovki->";

for(int i=t;i<=qt;i++)

{cout<<qwe[i].name<<" ";}

cout<<endl;

system(pause);

return 0;

}

6

 

2 Описание программы

2.1 Общие сведения

Программа N_sort «Сортировка естественным двухпутевым слиянием слиянием по алгоритму N» написана на языке C++. Для функционирования программы необходима операционная система Microsoft Windows XP и выше.

2.2 Функциональное назначение

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

2.3 Описание логической структуры

Программа реализует алгоритм N сортировки естественным двухпутевым слиянием [1, 3]:

N1. [Начальная установка.] Установить s ← 0. (При s = 0 записи из области (Ri+1, …, RN) пересылаются в область (RN+i, ..., R2N); при s = 1 об­ласти по отношению к пересылкам поменяются ролями.)

N2. [Подготовка к просмотру.] Если s = 0, то присвоить i ← 1, j ← N, k ← N + 1, l ← 2N. Если s = 1, то присвоить i ← N + 1, j ← 2N, k ← 1, I ← N. (Переменные i, j, k, l указывают текущие позиции во входных фай­лах, откуда идёт чтение, и в выходных файлах, куда идёт запись.) При­своить d ←1, f ← 1. (Переменная d определяет текущее направление выво­да, устанавливается равной 0, если необходимы дальнейшие просмотры.)

N3. [Сравнение Ki и Ki.] Если Ki > Ki, то перейти к шагу N8. Если i = j, то присвоить Rk ← Ri и перейти к шагу N13.

7

N4. [Пересылка Ri.] Установить Rk ← Ri, k ← k + d.

N5. [Ступенька вниз?] Увеличить i на 1. Затем, если Ki-1 £ Кь то вер­нуться к шагу N3.

N6. [Пересылка Ri] Присвоить Rk ← Rj, k ← k + d.

N7. [Ступенька вниз?] Уменьшить j на 1. Затем, если Ki+1 £ Кj то вернуться к шагу N6; в противном случае перейти к шагу N12.

N8. [Пересылка Ri] (Шаги N8...NH двойственны по отношению к шагам N4...N7 Установить Rk ← Ri, k ← k + d.

N9. [Ступенька вниз?] Уменьшить j на 1. Затем, если Ki+1 £ Кj, то вернуться к шагу N3.

N10. [Пересылка Ri.] Присвоить Rk ← Ri, k ← k + d.

N11. [Ступенька вниз?] Увеличить i на 1. Затем, если Ki-1 £ Кi, то вернуться к шагу N10.

N12. [Переключение направления.] Присвоить f ← 0, d ← −d и

взаимозаменить к ← l. Вернуться к шагу N3.

N13. [Переключение областей.] Если f = 0, то присвоить s ← 1 − s и вернуться к шагу N2. В противном случае сортировка завершена; если s = 0, то присвоить (R1 ..., RN.) ← (RN+l, ..., R2N). (Если результат можно оставить в области (RN+l, ..., R2N) то выполнение последнего копирования необязательно.) ■

Этот алгоритм предполагает ввод положительного целого числа n − размерность множества, а также ввод элементов записей, которые являются целыми числами и строками.

Программа использует методы последовательного распределения памяти.

8

Она содержит директивы #include и главную функцию main. Директивы #include вставляют в код программы файлы iostream.h, stdio.h, fstream, string и math.h с описанием стандартных функций языка C++.

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

Функция main формирует начальное распределение памяти, ввод вывод элементов массива, сортировки массива.

2.4 Используемые технические средства

PC-совместимый компьютер следующей минимальной конфигурации: процессор с тактовой частотой не ниже 800 МГц и объемом оперативной памяти не ниже 512 Мбайт.

2.5 Вызов и загрузка

Вызов и загрузка осуществляется запуском файла программы N_sort.exe с прилагаемого сменного оптического носителя типа CD−R.

9

 

2.6 Входные данные

Входными данными программы являются число n − количество элементов массива и n записей, которые представляют собой структуру состоящую из целого числа и строки.

2.7 Выходные данные

Выходными данными является массив отсортированных элементов по возрастанию относительно чисел factor.

3 Описание применения

3.1 Назначение программы

Программа предназначена для выполнения сортировки естественным двухпутевым слиянием массива мощности n, элементы которого пронумерованы числами от 1 до n.

3.2 Условия применения

Для выполнения программы необходим PC-совместимый компьютер с процессором тактовой частоты не ниже 800 МГц и объемом оперативной памяти не ниже 512 Мбайт, с установленной операционной системой Microsoft Windows XP и выше.

Входными данными программы являются число n − количество элементов массива и n записей, которые представляют собой структуру состоящую из целого числа и строки.

Выходными данными является массив отсортированных элементов по возрастанию относительно чисел factor.

3.3 Описание задачи

Задача сортировки естественным двухпутевым слиянием по алгоритму N заключается в том, чтобы расположить элементы массива, по возрастанию относительно чисел factor используя меньше времени.

3.4 Входные и выходные данные

10

Входными данными программы являются число n − количество элементов массива и n записей, которые представляют собой структуру состоящую из целого числа и строки.

Выходными данными является массив отсортированных элементов по возрастанию относительно чисел factor.

11

 

4 Тестовый пример

Для входных данных n = 4; factor[1] = 5, factor[2] = 20, factor[3] = 15, factor[4] = 10; name[1] = ”Это”, name[2] = ”работа.”, name[3] = ”курсовая”, name[4] = ”моя” программа должна отсортировать массив по возрастанию относительно чисел factor алгоритмом M обменной сортировки со слиянием.

Успешное прохождение программой N_sort.exe этого теста подтверждает снимок экрана, изображённый на рис. 1.

Рисунок 1 – Результат тестирования программы

12

 

Заключение

Разработана программа N_sort.exe обменной сортировки со слиянием по алгоритму N. Тестирование программы подтвердило её работоспособность.

Курсовая работа оформлена в соответствии со стандартом предприятия СТП ТГТУ 07-97, введенным с 1 января 1998 г., который устанавливает единые правила и порядок оформления дипломных (курсовых) проектов (работ), выполняемых студентами Тамбовского государственного технического университета и является обязательным для преподавателей и студентов университета [9].

13

Список используемых источников

1. Методы программирования: учебное пособие / , , [и др.]. – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2012. – 144 с.

2. Кулаков, программирования [Электронный ресурс]: Программа, методические указания и задания / , . – Тамбов: Издательство ТГТУ, 2006. – 32 с. – Режим доступа: http://window. *****/window_catalog/files/r38632/kulakov. pdf.

3. Кнут, Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы / Д. Кнут. – М. : Мир, 1976. – 736 с.

4. Макконнелл, Д. Основы современных алгоритмов / Д. Макконнелл. − М.: Техносфера, 2004. − 368 с.

5. Нивергельт, Ю. Машинный поход к решению математических задач / Ю. Нивергельт, Д. Фаррар, Э. Рейнголд. − М.: Мир, 1977. − 352 с.

6. Новиков, математика для программистов / Ф. А. Новиков. − СПб.: Питер, 2004. − 302 с.

7. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. − М.: Техносфера, 2005. − 400 с.

8. Уайс, структур данных и решение задач на C++ / . − М.: ЭКОМ Паблишерз, 2008. − 896 с.

9. Стандарт предприятия. Проекты (работы) дипломные и курсовые. Правила оформления. − Тамбов: Изд-во ТГТУ, 2003. − 40 с.

14