Файл: Сортировка слиянием без копирования.pdf

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

Один из методов реализации этого подхода заключается в применении двух вариантов программ:

– для приема исходных данных и для пересылки выходных данных в файл,

– для приема начальных данных в файл и пересылки выходных в конечный файл.

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

Такую потерю можно восполнить при использовании реализации той же описанной идеи: надо писать программу как алгоритм слияния, одну для представления определенного массива в порядке его возрастания, а иную – для представления компонентов массива в порядке их убывания. Вооружившись такой методикой, можно снова обратиться рекурсивно к ней и устроить так, чтобы внутреннему циклу слияния не понадобились никогда служебные метки. [11]

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

Рекурсивная программа предусматривает выполнение сортировки файла b, а результат сортировки будет помещаться в файл а. В результате, рекурсивные вызовы сформулированы так, что их результаты будут оставаться в файле b и в файле а.

Таким образом, все такие перемещения данных выполняются при реализации слияния.

Листинг алгоритма приведен ниже:

template <class Item>

void mergeAB(Item c[], Item a[], int N, Item b[], int M ) {

for (int i = 0, j = 0, k = 0; k < N+M; k++) {

if (i == N) { c[k] = b[j++]; continue; }

if (j == M) { c[k] = a[i++]; continue; }

c[k] = (a[i] < b[j]) ? a[i++] : b[j++];

}

}

template <class Item>

void mergesortABr(Item a[], Item b[], int l, int r) {

if (r-l <= 10) { insertion(a, l, r); return; }

int m = (l+r)/2;

mergesortABr(b, a, l, m);

mergesortABr(b, a, m+1, r);

mergeAB(a+l, b+l, m-l+1, b+m+1, r-m);

}

ЗАКЛЮЧЕНИЕ

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

Отметим, что рассмотренные циклы с постусловием будут выполняться всегда хотя бы 1 раз, а цикл с предусловием – не выполняется ни разу, если условие будет ложным.

Данные 2 вида циклических операторов являются самыми основными в ЯП высокого уровня.

Для реализации разнообразных циклических схем на высокоуровневых ЯП вводятся операторы для осуществления перехода, что могут применяться только внутри самых циклов.

Стоит отметить, что они позволяют выполнять выход с цикла принудительно или может его продолжать. В процессе применения циклов до полного их завершения также могут возникать дополнительные условия.

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

Программировать на С ++ можно как для Windows, так и для Unix, причем для каждой из операционных систем существует значительное количество средств разработки: от компиляторов до мощных интерактивных сред, как, например, Borland С ++ Builder, Microsoft Visual C ++ или Visual Studio .NET.

В процессе написания курсовой работы рассмотрены примеры использования алгоритма сортировки.

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

В процессе написания курсовой работы были реализованы следующие задачи:

– рассмотреть понятие алгоритма и терминологии, которая с ним связана;

– выполнить описание операторов цикла на С++;

– рассмотреть применение массивов в С++, как объекта сортировки;

– рассмотреть основные типы сортировки данных;

– дать характеристику и на практике описать программу для сортировки методом слияния без копирования.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Динман М.И. С++. Освой на примерах. – СПб.: БХВ-Петербург, 2012.– 260 с.
2. Дэвид Гриффитс, Дон Гриффитс. Изучаем программирование на С. Издательство «Эксмо». – 2013. – 400 с.
3. Кнут, Дональд, Эрвин. Искусство программирования. Том : Уч. пос. М.: Издательский дом. «Вильямс», 2014.– 720с.
4. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход. – СПб.: БХВ-Петербург, 2013. – 464с.
5. Лаптев В.В. С++. Объектно-ориентированное программирование. Задачи и упражнения. – СПб.: Питер. 2013. – 288 с.
6. Майерс С. Эффективное использование С++. – М.: ДМК Пресс; – СПб.: Питер. 2013.–240с.
7. Прата С. Язык программирования С++. Издание 6. Издательский дом «Вильямс» – 2016. – 304 с.
8. Р. Лафоре. Объектно-ориентированное программирование в С++. Издательство «Питер». Издание 4. – 2014. – 628 с.
9. С++ Стандартная библиотека. Для профессионалов./Н. Джосьютис. – СП Питер, 2012. – 350 с.
10. Седжвик Роберт. Фундаментальные алгоритмы на С++. К.: Издательство «ДиаСофт», – 2014. – 500 с.
11. Скляров В.А. Язык С++ и объектно-ориентированное программирование. – Минск. «Вышейшая школа». – 2012. – 478с.
12. Харви Дейтел, Пол Дейтел. Как программировать на С++. Пер. с англ. – М.: ЗАО «Издательство БИНОМ», 2012. – 430 с.
13. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб. пособие. – Финансы и статистика, 2014. – 464с.
14. Штерн Виктор. Основы С++: Методы программной инженерии.– Издательство «Лори», 2013. – 860с.
15. Язык С++: Учеб. Пособие /И.Ф. Астахова, С.В. Власов, В.В. Фертиков, А.В. Ларин.–Мн.: Новое знание, 2013. – 203 с.