Сортировка слиянием. Курсовая работа (т). Информационное обеспечение, программирование.
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Информационное обеспечение, программирование
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!
Похожие работы на - Сортировка слиянием
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Скачать Скачать документ
Информация о работе Информация о работе
Нужна качественная работа без плагиата?
Не нашел материал для своей работы?
Поможем написать качественную работу Без плагиата!
Министерство образования и науки
Российской Федерации
Федеральное государственное бюджетное
образовательное учреждение
высшего профессионального образования
«Тульский государственный
педагогический университет им. Л.Н.Толстого»
(ФГБОУ ВПО «ТГПУ им. Л.Н. Толстого »)
Кафедра информатики и информационных
технологий
по дисциплине «Основы
программирования»
факультета
Математики, Физики и Информатики
направления
«Фундаментальная информатика и информационные системы»
профиля
«Открытые информационные системы»
Глава 1. Алгоритм сортировки слиянием
.2 Алгоритм сортировки простым слиянием
.3 Алгоритм сортировки естественным слиянием
Глава 2. Реализация алгоритмов сортировки слияниями
.1 Программная реализация простого слияния
.2 Программная реализация естественного слияния
.1 Тестирование меню на корректность входных данных
Необходимость отсортировать какие-либо величины возникает в
программировании довольно часто. К примеру, входные данные подаются
«вперемешку», а программе удобнее обрабатывать упорядоченную
последовательность. Существуют ситуации, когда предварительная сортировка
данных позволяет сократить содержательную часть алгоритма в разы, а время его
работы - в десятки раз.
Сколь бы хорошими и эффективными не был выбранный вами алгоритм, но если
в качестве подзадачи он использует «плохую» сортировку, то вся работа по его
оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных
данных способна заметно понизить эффективность алгоритма в целом.
Данная курсовая работа посвящена рассмотрению одного из важных методов
сортировки данных - сортировке методом слияний. Сортировка методом слияний
является одним из наиболее известных алгоритмов внешних сортировок -
сортировок, требующих для работы внешней памяти компьютера.
Данные, хранящиеся на внешних устройствах, имеют больший объём, что не
позволяет их целиком переместить в оперативную память, отсортировать с
использованием одного из алгоритмов внутренней сортировки, а затем вернуть их
во внешнее устройство.
Цель данной курсовой работы: рассмотрение алгоритмов сортировок методом
слиянием.
В ходе этой курсовой работы рассмотрены следующие вопросы:
понятие сортировки и алгоритма сортировки;
критерии оценивания алгоритмов сортировок;
классификация алгоритмов сортировок;
рассмотрение и анализ основных понятий сортировок слияниями;
описание методов простого и естественного слияний;
описание программ, реализующих алгоритмы сортировки простым слиянием и
естественным слиянием.
Для демонстрации данных алгоритмов выбран С++ - высокоуровневый и
современный язык программирования, предназначенный для решения широкого класса
задач. Эти алгоритмы рассмотрены в среде программирования Microsoft Visual Studio 2010.
Глава 1. Алгоритм сортировки слиянием
Алгоритм сортировки слияниями был изобретён венгеро-американским
математиком Джоном фон Нейманом в 1945 году. Он является одним из самых быстрых
способов сортировки.
Слияние - это объединение двух или более упорядоченных массивов в один
упорядоченный.
Сортировка слияниями является одним из самых простых алгоритмов
сортировки (среди быстрых алгоритмов). Особенностью этого алгоритма является
то, что он работает с элементами массива преимущественно последовательно,
благодаря чему именно этот алгоритм используется при сортировке в системах с
различными аппаратными ограничениями (например, при сортировке данных на
жестком диске). Кроме того, сортировка слиянием является алгоритмом, который
может быть эффективно использован для сортировки таких структур данных, как
связанные списки.
Данный алгоритм применяется тогда, когда есть возможность использовать
для хранения промежуточных результатов память, сравнимую с размером исходного
массива. Он построен на принципе «разделяй и властвуй». Сначала задача
разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с
помощью рекурсивного вызова или непосредственно, если их размер достаточно мал.
Далее их решения комбинируются, и получается решение исходной задачи.
Процедура слияния требует два отсортированных массива. Заметим, что
массив из одного элемента по определению является отсортированным.
Введём понятие упорядоченного отрезка или серии - это последовательность
элементов, для которых не нарушается условие упорядоченности. Количество
элементов данной последовательности называется длиной серии. Серия, состоящая
из одного элемента, упорядочена всегда. Если длина серии фиксирована, то
слияние называется простым. При естественном слиянии всегда сливаются две
наиболее длинных серии.
Фаза - это последовательность действий, необходимых для однократной
обработки всех элементов.
Проход - это наименьший процесс, реализация которого составляет алгоритм
сортировки.
Двухфазная сортировка - это сортировка, в которой отдельно реализуется
две фазы: распределение и слияние. Однофазная сортировка - это сортировка, в
которой объединены фазы распределения и слияния в одну.
Исходные данные разбиваются на серии, или упорядоченные отрезки, и
распределяются на два и более вспомогательных массива. Это распределение идет
поочередно: первая серия записывается в первый вспомогательный массив, вторая -
во второй и т.д. После того, как произошла запись серии в последний
вспомогательный массив, следующая по счёту серия записывается опять в первый
вспомогательный массив. После распределения всех серий они объединяются в более
длинные упорядоченные отрезки: из каждого вспомогательного массива берется по
одной серии, и серии сливаются. Если в каком-то массиве серия заканчиваются, то
следующая серия пока не рассматривается. Сформированный более длинный
упорядоченный отрезок записывается либо в исходный массив, либо в какой-то из
вспомогательных. Далее происходит распределение этих длинных серий во
вспомогательные массивы с последующим их слиянием. До тех пор пока все данные
не будут упорядочены.
В сортировке слияниями выделяют две основные характеристики:
) Количество вспомогательных массивов. В случае если
вспомогательных массивов два, распределение называется двухпутевым, а вся
сортировка - двухпутевым слиянием.
) Количество фаз (шагов, этапов) в реализации сортировки.
Шаг 1. Разбить имеющиеся элементы массива на пары и осуществить слияние
элементов каждой пары, получив отсортированные цепочки длины 2 (кроме, быть
может, одного элемента, для которого не нашлось пары).
Шаг 2. Разбить имеющиеся отсортированные цепочки на пары, и осуществить
слияние цепочек каждой пары.
Шаг 3. Если число отсортированных цепочек больше единицы, перейти к шагу
2.
алгоритм слияние сортировка простой
Сортировка является важнейшей задачей программирования. Для её решения
разработано множество различных алгоритмов. В общем случае под сортировкой
следует понимать процесс расставления заданного множества объектов в
определённом порядке.
Алгоритм сортировки - это алгоритм для упорядочивания некоторого
множества элементов. Чаще всего упорядочивание происходит по возрастанию или по
убыванию. Алгоритмы сортировки находят широкое применение в различных областях
программирования: начиная от работы с огромными объёмами баз данных, заканчивая
составлением программ для решения математических задач.
Задачи, связанные с обработкой данных, решаются намного проще, если
множество данных заранее упорядочено.
Встречаются ситуации, когда во множестве элементов встречаются элементы с
одинаковыми значениями. Как правило, они располагаются рядом в любом порядке относительно
друг друга, но бывает полезным сохранять первоначальный порядок элементов с
одинаковыми значениями.
В алгоритмах сортировки часть данных используется в качестве ключа
сортировки - атрибута (или нескольких атрибутов), по значению которого определяется
порядок элементов. При написании алгоритмов сортировок массивов всегда следует
учесть, что ключ полностью или частично совпадает с данными.
Оценка алгоритмов проводится по следующим параметрам:
· Время сортировки - быстродействие алгоритма.
· Память - характеристика для временного хранения данных во
время выполнения алгоритма.
· Устойчивость - неизменность взаимного расположения элементов
с равными значениями.
· Естественность поведения - параметр, указывающий эффективен
ли алгоритм при сортировке уже отсортированного или частично отсортированного
множества данных. Если эта информация будет учтена при работе алгоритма, то он
будет менее затратным и более эффективным.
Выделяют алгоритмы внутренней и внешней сортировок. В первом случае для
временного хранения данных используется лишь оперативная память компьютера. Во
втором случае алгоритм сортировки использует внешнюю память компьютера (как
правило, жёсткие диски). Внешняя сортировка разработана для обработки больших
списков данных, которые не помещаются в оперативную память. Нелишним будет
отметить, что алгоритмы внутренней сортировки значительно эффективнее
алгоритмов внешней : на обращение к внутренней памяти компьютера затрачивается
намного меньше времени, чем к внешней. Если в какой-либо задаче имеется
возможность записать данные из внешней памяти в оперативную, то лучше
воспользоваться этой возможностью, и перейти от внешних сортировок к
внутренним.
.2 Алгоритм сортировки простым слиянием
На первом проходе сортируются пары соседних элементов исходного массива.
Затем осуществляется слияние соседних пар, после этого четвёрок, восьмёрок и
т.д. Трудоёмкость такого метода в общем случае определяется по формуле n * log2 n,
однако данную сортировку достаточно сложно реализовать, не задействовав
дополнительную память, поэтому сортировку слияниями следует использовать тогда,
когда количество элементов массива сопоставимо с задействованными ресурсами
дополнительной памяти.
-2 0 -6 3 1 -5
Сортировка простым слиянием заканчивается если:
)после фазы слияния длина серии не меньше количества элементов в массиве;
)на фазе слияния осталась ровно одна серия;
)второй по счёту вспомогательный массив для однофазной сортировки остался
пустым.
//Описание функции сортировки простым слиянием
void p_sort(int *Mas, int first, int last)
{_sort(Mas, first, (first+last)/2);
//сортировка левой части_sort(Mas, (first+last)/2+1, last);
//сортировка правой части_mass(Mas, first, last);
Листинг 1.Алгоритм сортировки простым слиянием
.3 Алгоритм сортировки естественным слиянием
Всегда сливаются две самые длинные серии из всех возможных. Признаком
конца серии в этом случае служит результат сравнения двух соседних элементов.
Серия заканчивается, если очередной элемент меньше предыдущего.
М1: 1 3 14 2 4 5 7 11 М2: 6
8 9 10 16
М1: 1 3 6 8 9 14 М2: 2 4 5
7 10 11 16
Естественное слияние заканчивается тогда, когда:
)на фазе слияния осталась ровно одна серия;
)второй по счёту вспомогательный массив для однофазной сортировки после
распределения серии остался пустым.
Естественное слияние может оказаться несбалансированным. Это произойдёт в
том случае, если количество серий, записанных во вспомогательные массивы, будет
существенно отличаться друг от друга.
Естественное слияние сбалансировано, когда после фазы распределения
количество серий во вспомогательных массивах отличается не более чем на
единицу.
//Описание функции сортировки естественным слиянием
{k1, k2, st, u, fl;* tm1 = new int[q];
// временный массив 1* tm2 = new int[q];
{=0;
((x[u+st-1]<=x[u+st]) &&(u+st-1 < q)) //
выбираем возрастающие цепочки элементов.
}((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))
}=u;=st+k1;=0;((x[u+st-1]<=x[u+st]) &&(u+st-1 <
q))
// аналогичным образом формируем второй массив
}((x[u+st-1]>= x[u+st]) || (u+st-1 == q-1))
}=u;=st+k2;(u > 0)(k1, k2, tm1, tm2, x);
Листинг 2.Алгоритм сортировки естественным слиянием
Единственного эффективнейшего алгоритма сортировки нет, ввиду множества
параметров оценки эффективности:
1)
Время - основной параметр, характеризующий быстродействие алгоритма. Называется
также вычислительной сложностью
<#"871515.files/image002.jpg">
Результат выполнения программы сортировки простым слиянием
Результат выполнения программы сортировки естественным слиянием
Похожие работы на - Сортировка слиянием Курсовая работа (т). Информационное обеспечение, программирование.
Курсовая работа по теме Анализ финансовых показателей предприятия (на примере ООО ТК 'Алекс')
Курсовая Работы Исследование Услуг Салона Красоты
Сочинение: Методы земской статистики как основа современных социологических исследований
Краткая История Олимпийских Игр Реферат По Физкультуре
Реферат На Тему Политика Формирования Инвестиционных Ресурсов Предприятия
Ленин Полное Собрание Сочинений 4 Издание
Курсовая Работа На Тему Внешняя Политика России: Исторический Анализ Начала Xx Века
Картина На Террасе Шевандронова Сочинение 8 Класс
Курсовая работа: Особенности памяти младших школьников. Скачать бесплатно и без регистрации
Курсовая работа по теме Бухгалтерские стандарты
Сочинение: Ташкент. Скачать бесплатно и без регистрации
Курсовая работа по теме Проектирование аналогового электронного устройства
Реферат: Готическая архитектура. Скачать бесплатно и без регистрации
Сочинение Преступление И Наказание Образ Петербурга
Курсовая работа: Проблема застенчивости в подростковом возрасте
Контрольная работа по теме Производство дознания пограничными органами ФСБ России
Какие Книги Читают В 21 Веке Сочинение
Практическое задание по теме Роман 'Евгений Онегин' (доклад)
Курсовая работа по теме Транспортные тарифы и факторы на них влияющие на примере предприятия ООО 'РостаТранс'
Реферат: Классификация управленческих решений 4
Реферат: Маркетинговый анализ конкурентоспособности водки
Книга: Введение в теологию
Курсовая работа: Статистико-экономический анализ производства кормов на предприятии