книги / Технологии разработки объектно-ориентированных программ на язык C++. Основы структурного программирования на алгоритмическом языке C++

Исключаем первый элемент из обработки.

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

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

Задание для самостоятельной работы:

Написать программный код для сортировки методом выбора. Количество элементов в массиве и их значения задает пользователь.

15.6.Сортировки методами естественного

имногофазного слияния

Сортировка методом естественного слияния

Данный метод (рис. 15.9) считается одним из самых эффективных методов внешней сортировки – данные хранятся не в массивах в программе, а в отдельном файле.

Исходный файл f:

Распределение

Слияние

1-й проход

2-й проход

3-й проход

Рис. 15.9. Сортировка методом естественного слияния

Алгоритм:

Исходный массив разбивается на два файла следующим образом: разбивкой на упорядоченные серии. Пока элементы находятся по возрастанию или повторяются, это одна серия, которая записывается в один файл. Следующая серия – во второй. Третья серия – в первый файл, но строкой ниже и т.д. Например, строка 2 7 8 4 10 1

191

17 разобьется следующим образом. Первый файл: 2 7 8, 1 17; второй файл: 4 10.

Из вспомогательных файлов все серии соединяются обратно следующим образом: берутся первые серии из первого и второго файлов. По элементам сравниваются и сортируются – в исходный файл записывается сумма этих серий, уже отсортированная. Аналогично происходит с остальными парами серий, которые приписываются в конец строки в исходном файле. Если у одной из серий нет пары, то она просто записывается в конец строки. Например, первый файл: 2 7 8, 1 17; второй файл: 4 10. Отсортированная сумма первых двух серий даст 2 4 7 8 10. У следующей серии нет пары – приписываем ее в конец и получаем 2 4 7 8 10 1 17.

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

Задание для самостоятельной работы:

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

Сортировка методом многофазного слияния

Данная сортировка (рис. 15.10) считается самой эффективной из внешних сортировок.

Алгоритм:

Первый шаг аналогичен шагу из сортировки естественным слиянием. Исходный массив разбивается на несколько файлов следующим образом: разбивкой на упорядоченные серии. Пока элементы находятся по возрастанию или повторяются, это одна серия, которая записывается в один файл. Следующая серия – во второй. Третья серия – в третий файл и т.д.

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

192

элементом в нем становится следующий. Например, в трех файлах содержатся серии: 3 17 23, 1 4 9, 5 10. В начало главной серии встает элемент 1, а в файлах остаются 3 17 23, 4 9, 5 10.

Повторяется второй шаг, но элемент становится уже в конец текущей главной серии. Закончить, как только в файлах не останется элементов.

Рис. 15.10. Сортировка методом многофазного слияния

Задание для самостоятельной работы:

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

193

СПИСОК ЛИТЕРАТУРЫ

1.Буч Г. Объектно-ориентированный анализ и проектирование

спримерами на С++. – М.: БИНОМ, 1998. – 560 с.

2.Ваныкина Г.В., Сундукова Т.О. Алгоритмы компьютерной обработки данных: учебное пособие. – Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого, 2011. – 219 с.

3.Гольдштейн А.Л. Теория принятия решений. Задачи и методы исследования операций и принятия решений: учебное пособие. – 2-е изд., испр. – Пермь: Изд-во Перм. гос. техн. ун-та, 2009. – 361 с.

4.Давыдов В.Г. Программирование и основы алгоритмизации. –

М., 2003. – 447 с.

5.Джамса К. Учимся программировать на языке С++. – М.: Мир,

1997. – 320 с.

6.Крупник А.Б. Самоучитель С++. – СПб.: Питер, 2005. – 233 с.

7.Мамонова Т.Е. Информатика. Общая информатика. Основы языка C++: учебное пособие. – Томск: Изд-во Том. политехн. ун-та,

2011. – 206 с.

8.Мейн М., Савитч У. Структуры данных и другие объекты в C++: пер. с англ. – 2-е изд. – М.: Вильямс, 2002. – 832 с.

9.Ноткин А.М. Объектно-ориентированное программирование: ООП на языке С++: учебное пособие. – Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2013. – 230 с.

10.Павловская Т.А. C/C++. Программирование на языке высокого уровня. – СПб.: Питер, 2007 – 461 с.

11.Павловская Т.А., Щупак Ю.А. C++. Объектно-ориенти- рованное программирование: практикум. – СПб., 2006. – 265 с.

12.Подбельский В.В. Язык Си++: учебное пособие. – М.: Финансы и статистика, 1996. – 560 с.

13.Скиена С. Алгоритмы. Руководство по разработке: пер.

сангл. – 2-е изд. – СПб.: БХВ-Петербург, 2011. – 720 с.

14.Стивен Прата. Язык программирования C++: лекции и упражнения: пер. с англ. – 6-е изд. – М.: Вильямс, 2012. – 1248 c.

194

15.Страуструп Б. Языки программирования С++. – СПб.: БИ-

НОМ, 1999. – 991 с.

16.Топп У., Форд У. Структуры данных в C++: пер. с англ. –

М.: БИНОМ, 1999. – 816 с.

17.Шмидский Я.К. Программирование на языке C/C++. Самоучитель. – М.: Вильямс, 2004. – 368 с.

18.C++ Reference. – URL: http://www.cplusplus.com/reference (accessed 20 April 2018).

19.Cppstudio. Двусвязные списки в С++ [Электронный ре-

сурс]. – URL: http://cppstudio.com/post/8482/ (дата обращения: 16.07.2018).

20.Cppstudio. Очередь в С++ [Электронный ресурс]. – URL: http://cppstudio.com/post/8487/ (дата обращения: 16.07.2018).

21.Cppstudio. Структура данных: стеки [Электронный ресурс]. – URL: http://cppstudio.com/post/5155/ (дата обращения: 17.07.2018).

22.Библиотека GLUT. Урок 7. Работа с мышью [Электронный ре-

сурс]. – URL: http://grafika.me/node/133 (дата обращения: 16.05.2018).

23.Знакомимся с OpenGL [Электронный ресурс]. – URL: https://habr.com/post/111175/ (дата обращения: 16.05.2018).

24.Как использовать шрифты в GLUT? [Электронный ресурс].

–URL: http://programmingcpp.narod.ru/font_in_GLUT.htm (дата об-

ращения: 16.05.2018).

25.НОУ ИНТУИТ. Лекция 38: Алгоритмы поиска в линейных структурах [Электронный ресурс]. – URL: https://www.intuit.ru/ studies/courses/648/504/lecture (дата обращения: 17.08.2018).

195

Учебное издание

Полякова Ольга Андреевна, Викентьева Ольга Леонидовна

ТЕХНОЛОГИИ РАЗРАБОТКИ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ПРОГРАММ НА ЯЗЫКЕ С++

В двух частях

Часть I

Учебное пособие

Редактор и корректор Е.Б. Денисова

Подписано в печать 19.06.2019. Формат 60×90/16. Усл. печ. л. 12,25. Тираж 50 экз. Заказ № 99/2019.

Издательство Пермского национального исследовательского

политехнического университета.

Адрес: 614990, г. Пермь, Комсомольский пр., 29, к. 113.

Тел. [phone]

196