Внешняя сортировка. Метод сбалансированного слияния

Сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле являются оптимальными, а большинство имеет какие-либо преимущества по сравнению с остальными [5]. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, и в случае сортировки она настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ; для этой памяти характерен быстрый произвольный доступ, а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е.

---

Не бойтесь заказать реферат в Красноярске , у нас работают профессионалы

---

на запоминающих устройствах. Это существенное различие можно наглядно показать на примере сортировки пронумерованных карточек. Представление карточек в виде массива соответствует тому, что все они располагаются перед сортирующим так, что каждая карточка видна и доступна. Представление карточек в виде файла предполагает, что видна только верхняя карточка из каждой стопки. Очевидно, что такое ограничение приведет к существенному изменению методов сортировки, но оно неизбежно, если карточек так много, что их число на столе не уменьшается. Целью данной курсовой работы является рассмотрение методов внешней сортировки, процесса сортировки методом сбалансированного слияния. Задачи: • изучить понятие сортировки и алгоритма сортировки; • изучить алгоритмы сортировок; • рассмотреть и проанализировать основные понятия сортировок слияниями; • описать общую схему слияний; • описать методы простого и естественного слияний; • описать программу, реализующую алгоритм сортировки естественным (сбалансированным) слиянием. Объектом исследования является алгоритм метода сбалансированного слияния. Предметом исследования является алгоритм метода сбалансированного слияния, реализованный в программе. Методы исследования, используемые при выполнении задания курсовой работы: метод анализа и метод моделирования. Для демонстрации данных алгоритмов выбран С# - высокоуровневый и современный язык программирования, предназначенный для решения широкого класса задач. Эти алгоритмы рассмотрены в среде программирования Microsoft Visual Studio 2019. Структура работы состоит из нескольких элементов: введения, теоретической главы, практической главы, заключения, списка использованных источников, а также приложения. Введение содержит актуальность работы, цель, задачи, а также структуру курсовой работы. Первая глава содержит теоретические основы о сортировках и методах сортировки. Вторая глава содержит практическую часть, программную реализацию метода сортировки. Заключение содержит выводы по проделанной работе. Список использованных источников содержит ссылки на материалы, которые были использованы при написании работы.  

В ходе данной курсовой работы были рассмотрены вопросы, связанные с сортировкой данных методом слияний. Были рассмотрены и проанализированы основные понятия сортировок слияниями: серия, фаза, слияние, простое слияние, естественное слияние. Была описана общая схема слияний и дано её описание на простом примере. Также был разработан и подробным образом рассмотрен код программы, реализующей алгоритм сортировки методом естественного (сбалансированного )слияния. Цель данной курсовой работы достигнута - рассмотрены методы внешней сортировки, рассмотрен процесс сортировки методом сбалансированного слияния. Для достижения поставленной цели были выполнены следующие задачи: • изучено понятие сортировки и алгоритма сортировки; • приведены алгоритмы сортировок; • рассмотрены и проанализированы основные понятия сортировок слияниями; • описана общая схема слияний; • описаны методы простого и естественного слияний; • описана программа, реализующая алгоритм сортировки естественным (сбалансированным) слиянием. Метод сортировок слияниями является алгоритмом внешней сортировки данных, и потому применяется лишь при обработке огромных массивов информации (баз данных и пр.). Данные методы могут быть усовершенствованы в ходе основных критериев, рассмотренных в курсовой работе: памяти, естественности, времени и устойчивости.

1. Терехов А.Н. Технология программирования: Уч. пособ./ А.Н. Терехов.- М.: Интернет-университет информационных технологий.- 2007. - 148 с. 2. Лабораторный практикум по технологии программирования: Учебное по-собие /А.Ф. Рогачев и др.- Воронеж: Научная книга.- 2008.- 188 с. 3. Павловская Т.А. С/С++. Программирование на языке высокого уровня. СПб.:Питер, 2002 – 464 с. 4. Смирнов, А.А. Технологии программирования [Электронный ресурс]: учебное пособие/ Смирнов А.А., Хрипков Д.В.— Электрон. текстовые дан-ные.— М.: Евразийский открытый институт, 2011.— 191 c. 5. Гаспариан, М.С. Информационные системы и технологии [Электронный ресурс]: учебное пособие/ Гаспариан М.С., Лихачева Г.Н.— Электрон. тексто-вые данные.— М.: Евразийский открытый институт, 2011.— 370 c. 6. Брауде Э. Технология разработки программного обеспечения / Э. Брауде. – СПб.: Питер, 2004. – 655с. 7. Вирт Н. Алгоритмы и структуры данных / Н. Вирт. – 2-е изд. – СПб.: Невский диалект, 2001. – 352 с. 8. Кнут Д., Искусство программирования для ЭВМ. В 3 т. Т. 1. Основные алгоритмы / Д. Кнут. – 2-е изд. – М.: ИД “Вильямс”, 2002. – 720 с. 9. Кнут Д., Искусство программирования для ЭВМ. В 3 т. Т. 2. Получис-ленные алгоритмы / Д. Кнут. – 3-е изд. – М.: ИД “Вильямс”, 2003. – 832 с. 10. Кнут Д., Искусство программирования для ЭВМ. В 3 т. Т. 3. Сортировка и поиск / Д. Кнут. – 2-е изд. – М.: ИД “Вильямс”, 2001. – 832 с.