Слайд 2Определение
Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов.
Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания
![Определение Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-1.jpg)
множества элементов по возрастанию или убыванию.
Слайд 3Определение
В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются
![Определение В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-2.jpg)
рядом друг за другом в любом порядке.
Однако иногда бывает полезно сохранять первоначальный порядок элементов с одинаковыми значениями.
Слайд 4Определение
В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки.
Ключом сортировки называется
![Определение В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-3.jpg)
атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными.
Слайд 5Определение
Практически каждый алгоритм сортировки можно разбить на 3 части:
сравнение, определяющее упорядоченность пары
![Определение Практически каждый алгоритм сортировки можно разбить на 3 части: сравнение, определяющее](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-4.jpg)
элементов;
перестановку, меняющую местами пару элементов;
сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.
Слайд 6Определение
Алгоритмы сортировки имеют большое практическое применение.
Их можно встретить там, где речь
![Определение Алгоритмы сортировки имеют большое практическое применение. Их можно встретить там, где](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-5.jpg)
идет об обработке и хранении больших объемов информации.
Некоторые задачи обработки данных решаются проще, если данные заранее упорядочить.
Слайд 7Оценка алгоритмов сортировки
Ни одна другая проблема не породила такого количества разнообразнейших решений,
![Оценка алгоритмов сортировки Ни одна другая проблема не породила такого количества разнообразнейших](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-6.jpg)
как задача сортировки.
Универсального, наилучшего алгоритма сортировки на данный момент не существует.
Слайд 8Оценка алгоритмов сортировки
Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным
![Оценка алгоритмов сортировки Однако, имея приблизительные характеристики входных данных, можно подобрать метод,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-7.jpg)
образом.
Для этого необходимо знать параметры, по которым будет производиться оценка алгоритмов.
Слайд 9Оценка алгоритмов сортировки
Время сортировки – основной параметр, характеризующий быстродействие алгоритма.
Устойчивость – это параметр, который
![Оценка алгоритмов сортировки Время сортировки – основной параметр, характеризующий быстродействие алгоритма. Устойчивость](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-8.jpg)
отвечает за то, что сортировка не меняет взаимного расположения равных элементов.
Слайд 10Оценка алгоритмов сортировки
Память – один из параметров, который характеризуется тем, что ряд алгоритмов
![Оценка алгоритмов сортировки Память – один из параметров, который характеризуется тем, что](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-9.jpg)
сортировки требуют выделения дополнительной памяти под временное хранение данных.
При оценке используемой памяти не будет учитываться место, которое занимает исходный массив данных и независящие от входной последовательности затраты, например, на хранение кода программы.
Слайд 11Оценка алгоритмов сортировки
Естественность поведения – параметр, которой указывает на эффективность метода при обработке
![Оценка алгоритмов сортировки Естественность поведения – параметр, которой указывает на эффективность метода](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-10.jpg)
уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Слайд 12Классификация алгоритмов сортировок
Все разнообразие и многообразие алгоритмов сортировок можно классифицировать по различным
![Классификация алгоритмов сортировок Все разнообразие и многообразие алгоритмов сортировок можно классифицировать по](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-11.jpg)
признакам, например, по устойчивости, по поведению, по использованию операций сравнения, по потребности в дополнительной памяти, по потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, и другие.
Слайд 13Классификация алгоритмов сортировок
Рассмотрим классификацию алгоритмов сортировки по сфере применения:
Внутренняя сортировка
Внешняя сортировка
![Классификация алгоритмов сортировок Рассмотрим классификацию алгоритмов сортировки по сфере применения: Внутренняя сортировка Внешняя сортировка](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-12.jpg)
Слайд 14Классификация алгоритмов сортировок
Внутренняя сортировка – это алгоритм сортировки, который в процессе упорядочивания данных
![Классификация алгоритмов сортировок Внутренняя сортировка – это алгоритм сортировки, который в процессе](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-13.jpg)
использует только оперативную память (ОЗУ) компьютера.
То есть оперативной памяти достаточно для помещения в нее сортируемого массива данных с произвольным доступом к любой ячейке и собственно для выполнения алгоритма.
Слайд 15Классификация алгоритмов сортировок
Внутренняя сортировка применяется во всех случаях, за исключением однопроходного считывания
![Классификация алгоритмов сортировок Внутренняя сортировка применяется во всех случаях, за исключением однопроходного](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-14.jpg)
данных и однопроходной записи отсортированных данных.
В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память.
Слайд 16Классификация алгоритмов сортировок
Внешняя сортировка – это алгоритм сортировки, который при проведении упорядочивания данных
![Классификация алгоритмов сортировок Внешняя сортировка – это алгоритм сортировки, который при проведении](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-15.jpg)
использует внешнюю память, как правило, жесткие диски.
Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память.
Слайд 17Классификация алгоритмов сортировок
Обращение к различным носителям накладывает некоторые дополнительные ограничения на данный
![Классификация алгоритмов сортировок Обращение к различным носителям накладывает некоторые дополнительные ограничения на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-16.jpg)
алгоритм: доступ к носителю осуществляется последовательным образом, то есть в каждый момент времени можно считать или записать только элемент, следующий за текущим; объем данных не позволяет им разместиться в ОЗУ.
Слайд 18Классификация алгоритмов сортировок
Внутренняя сортировка является базовой для любого алгоритма внешней сортировки – отдельные части
![Классификация алгоритмов сортировок Внутренняя сортировка является базовой для любого алгоритма внешней сортировки](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-17.jpg)
массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу.
Слайд 19Классификация алгоритмов сортировок
Следует отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение
![Классификация алгоритмов сортировок Следует отметить, что внутренняя сортировка значительно эффективней внешней, так](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-18.jpg)
к оперативной памяти затрачивается намного меньше времени, чем к носителям.
Слайд 20Глупая сортировка
Просматриваем массив слева-направо и по пути сравниваем соседей.
Если мы встретим
![Глупая сортировка Просматриваем массив слева-направо и по пути сравниваем соседей. Если мы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-19.jpg)
пару взаимно неотсортированных элементов, то меняем их местами и возвращаемся в самое начало массива. Снова проходим-проверяем массив, если встретили снова «неправильную» пару соседних элементов, то меняем местами и опять начинаем всё снова. Продолжаем до тех пор пока происходит обмен элементов.
Слайд 21Глупая сортировка
Пример работы алгоритма:
![Глупая сортировка Пример работы алгоритма:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-20.jpg)
Слайд 23Пузырьковая сортировка
Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — простой алгоритм сортировки.
Для понимания и
![Пузырьковая сортировка Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — простой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-22.jpg)
реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.
Слайд 24Пузырьковая сортировка
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо
![Пузырьковая сортировка Алгоритм считается учебным и практически не применяется вне учебной литературы,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-23.jpg)
него на практике применяются более эффективные алгоритмы сортировки.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву.
Слайд 25Пузырьковая сортировка
Пример работы алгоритма:
![Пузырьковая сортировка Пример работы алгоритма:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-24.jpg)
Слайд 26Пузырьковая сортировка
Обходим массив от начала до конца, попутно меняя местами неотсортированные соседние
![Пузырьковая сортировка Обходим массив от начала до конца, попутно меняя местами неотсортированные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-25.jpg)
элементы.
В результате первого прохода на последнее место «всплывёт» максимальный элемент.
Слайд 27Пузырьковая сортировка
Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего)
![Пузырьковая сортировка Теперь снова обходим неотсортированную часть массива (от первого элемента до](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-26.jpg)
и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте.
Слайд 28Пузырьковая сортировка
Продолжая также далее, будем обходить всё уменьшающуюся неотсортированную часть массива, помещая
![Пузырьковая сортировка Продолжая также далее, будем обходить всё уменьшающуюся неотсортированную часть массива,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-27.jpg)
найденные максимумы в конец.
Слайд 30Сортировка вставками
Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по
![Сортировка вставками Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-29.jpg)
одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Слайд 34Шейкерная сортировка
Сортировка перемешиванием, или Шейкерная сортировка, или двухсторонней сортировкой простыми обменами (англ. Cocktail
![Шейкерная сортировка Сортировка перемешиванием, или Шейкерная сортировка, или двухсторонней сортировкой простыми обменами](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-33.jpg)
sort) — разновидность пузырьковой сортировки.
Слайд 35Шейкерная сортировка
Производится многократный прогон по массиву, соседние элементы сравниваются и, в случае
![Шейкерная сортировка Производится многократный прогон по массиву, соседние элементы сравниваются и, в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-34.jpg)
необходимости, меняются местами. При достижении конца массива направление меняется на противоположное. Таким образом по очереди выталкиваются крупные и мелкие элементы массива в конец и начало структуры соответственно.
Слайд 38Сортировка чёт-нечет
Этот относительно простой алгоритм сортировки является модификацией пузырьковой сортировки.
Суть модификации в
![Сортировка чёт-нечет Этот относительно простой алгоритм сортировки является модификацией пузырьковой сортировки. Суть](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-37.jpg)
том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо.
Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.
Слайд 39Сортировка чёт-нечет
Заводится флаг, определяющий отсортирован ли массив. В начале итерации ставится в
![Сортировка чёт-нечет Заводится флаг, определяющий отсортирован ли массив. В начале итерации ставится](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-38.jpg)
состояние «истина», далее каждый нечётный элемент сверяется с последующим и если они стоят в не правильном порядке (предыдущий больше следующего), то они меняются местами, и флаг ставится в состояние «ложь». То же самое делается с чётными элементами. Алгоритм не прекращает работу, пока флаг не останется в состоянии «истина».
Слайд 42Сортировка расчёской
Сортировка расчёской (англ. comb sort) — это довольно упрощённый алгоритм сортировки, изначально спроектированный
![Сортировка расчёской Сортировка расчёской (англ. comb sort) — это довольно упрощённый алгоритм](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-41.jpg)
Влодзимежом Добосевичем в 1980г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine в апреле 1991г
Слайд 43Сортировка расчёской
В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы.
![Сортировка расчёской В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-42.jpg)
Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального.
Слайд 44Сортировка расчёской
Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё
![Сортировка расчёской Таким образом, мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-43.jpg)
более аккуратные пряди.
Слайд 45Сортировка расчёской
Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины,
![Сортировка расчёской Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-44.jpg)
называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247.
где е - экспонента; φ - "золотое" число
Слайд 46Сортировка расчёской
Сначала расстояние между элементами равно размеру массива, разделённого на фактор уменьшения
![Сортировка расчёской Сначала расстояние между элементами равно размеру массива, разделённого на фактор](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-45.jpg)
(результат округляется до ближайшего целого).
Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь.
Слайд 47Сортировка расчёской
Так продолжается до тех пор, пока разность индексов не достигнет единицы.
![Сортировка расчёской Так продолжается до тех пор, пока разность индексов не достигнет](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-46.jpg)
В этом случае массив досортировывается обычным пузырьком.
Слайд 50Гномья сортировка
Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но
![Гномья сортировка Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-49.jpg)
в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.
Слайд 51Гномья сортировка
Алгоритм находит первое место, где два соседних элемента стоят в неправильном
![Гномья сортировка Алгоритм находит первое место, где два соседних элемента стоят в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-50.jpg)
порядке и меняет их местами.
Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов.
Слайд 52Гномья сортировка
Он не допускает, что элементы после текущей позиции отсортированы, таким образом,
![Гномья сортировка Он не допускает, что элементы после текущей позиции отсортированы, таким](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-51.jpg)
нужно только проверить позицию до переставленных элементов.
Слайд 55Методы внешней сортировки
Внешняя сортировка – это сортировка данных, которые расположены на внешних
![Методы внешней сортировки Внешняя сортировка – это сортировка данных, которые расположены на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-54.jpg)
устройствах и не вмещаются в оперативную память.
К наиболее известным алгоритмам внешних сортировок относятся:
сортировки слиянием (простое и естественное слияние);
улучшенные сортировки (многофазная и каскадная сортировка).
Слайд 56Методы внешней сортировки
Из представленных внешних сортировок наиболее важным является метод сортировки с
![Методы внешней сортировки Из представленных внешних сортировок наиболее важным является метод сортировки](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-55.jpg)
помощью слияния.
Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.
Слайд 57Методы внешней сортировки
Количество элементов в серии называется длиной серии.
Серия, состоящая из одного
![Методы внешней сортировки Количество элементов в серии называется длиной серии. Серия, состоящая](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-56.jpg)
элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов.
Максимальное количество серий в файле N (все элементы не упорядочены).
Минимальное количество серий одна (все элементы упорядочены).
Слайд 58Методы внешней сортировки
Слияние – это процесс объединения двух (или более) упорядоченных серий в
![Методы внешней сортировки Слияние – это процесс объединения двух (или более) упорядоченных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-57.jpg)
одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.
Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.
Слайд 59Методы внешней сортировки
Фаза – это действия по однократной обработке всей последовательности элементов.
Двухфазная сортировка –
![Методы внешней сортировки Фаза – это действия по однократной обработке всей последовательности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-58.jpg)
это сортировка, в которой отдельно реализуется две фазы: распределение и слияние.
Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.
Слайд 60Методы внешней сортировки
Двухпутевым слиянием называется сортировка, в которой данные распределяются на два
![Методы внешней сортировки Двухпутевым слиянием называется сортировка, в которой данные распределяются на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-59.jpg)
вспомогательных файла.
Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N>2) вспомогательных файлов.
Слайд 61Общий алгоритм сортировки слиянием
Сначала серии распределяются на два или более вспомогательных файлов.
![Общий алгоритм сортировки слиянием Сначала серии распределяются на два или более вспомогательных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-60.jpg)
Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл, вторая – во второй и так далее до последнего вспомогательного файла.
Затем опять запись серии начинается в первый вспомогательный файл.
Слайд 62Общий алгоритм сортировки слиянием
После распределения всех серий, они объединяются в более длинные
![Общий алгоритм сортировки слиянием После распределения всех серий, они объединяются в более](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-61.jpg)
упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются.
Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется.
Слайд 63Общий алгоритм сортировки слиянием
В зависимости от вида сортировки сформированная более длинная упорядоченная
![Общий алгоритм сортировки слиянием В зависимости от вида сортировки сформированная более длинная](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-62.jpg)
серия записывается либо в исходный файл, либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение.
И так до тех пор, пока все данные не будут отсортированы.
Слайд 64Общий алгоритм сортировки слиянием
Основные характеристики сортировки слиянием:
количество фаз в реализации сортировки;
количество вспомогательных файлов,
![Общий алгоритм сортировки слиянием Основные характеристики сортировки слиянием: количество фаз в реализации](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-63.jpg)
на которые распределяются серии.
Слайд 65Сортировка простым слиянием
В данном алгоритме длина серий фиксируется на каждом шаге.
В исходном файле
![Сортировка простым слиянием В данном алгоритме длина серий фиксируется на каждом шаге.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-64.jpg)
все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2k.
Слайд 66Сортировка простым слиянием
Алгоритм сортировки простым слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.
Шаг
![Сортировка простым слиянием Алгоритм сортировки простым слиянием Шаг 1. Исходный файл f](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-65.jpg)
2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.
Слайд 67Сортировка простым слиянием
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и
![Сортировка простым слиянием Шаг 3. Полученный файл f вновь обрабатывается, как указано](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-66.jpg)
2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл.
Слайд 68Сортировка простым слиянием
Признаками конца сортировки простым слиянием являются следующие условия:
длина серии не
![Сортировка простым слиянием Признаками конца сортировки простым слиянием являются следующие условия: длина](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-67.jpg)
меньше количества элементов в файле (определяется после фазы слияния);
количество серий равно 1 (определяется на фазе слияния).
при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Слайд 70Сортировка простым слиянием
Пример: Пусть исходный файл f: 37824615
![Сортировка простым слиянием Пример: Пусть исходный файл f: 37824615](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-69.jpg)
Слайд 71Алгоритм сортировки естественным слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2. Распределение происходит
![Алгоритм сортировки естественным слиянием Шаг 1. Исходный файл f разбивается на два](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-70.jpg)
следующим образом: поочередно считываются записи ai исходной последовательности (неупорядоченной) таким образом, что если значения ключей соседних записей удовлетворяют условию f(ai) <= f(ai+1), то они записываются в первый вспомогательный файл f1.
Слайд 72Алгоритм сортировки естественным слиянием
Как только встречаются f(ai) > f(ai+1), то записи ai+1 копируются во второй
![Алгоритм сортировки естественным слиянием Как только встречаются f(ai) > f(ai+1), то записи](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-71.jpg)
вспомогательный файл f2.
Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.
Слайд 73Алгоритм сортировки естественным слиянием
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в
![Алгоритм сортировки естественным слиянием Шаг 2. Вспомогательные файлы f1 и f2 сливаются](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-72.jpg)
файл f, при этом серии образуют упорядоченные последовательности.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2.
Шаг 4. Повторяя шаги, сливаем упорядоченные серии до тех пор, пока не будет упорядочен целиком весь файл.
Слайд 74Алгоритм сортировки естественным слиянием
Символ "`" обозначает признак конца серии.
Признаками конца сортировки естественным
![Алгоритм сортировки естественным слиянием Символ "`" обозначает признак конца серии. Признаками конца](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-73.jpg)
слиянием являются следующие условия:
количество серий равно 1 (определяется на фазе слияния).
при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Слайд 75Алгоритм сортировки естественным слиянием
Естественное слияние, у которого после фазы распределения количество серий
![Алгоритм сортировки естественным слиянием Естественное слияние, у которого после фазы распределения количество](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-74.jpg)
во вспомогательных файлах отличается друг от друга не более чем на единицу, называется сбалансированным слиянием, в противном случае – несбалансированное слияние.
Слайд 76Алгоритм сортировки естественным слиянием
![Алгоритм сортировки естественным слиянием](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/867098/slide-75.jpg)