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

1.

Сортировка Слиянием
Презентацию и текст заготовили:
Матвеев Г. и
Новикова Н.

2.

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

3.

Исходный массив делится на две примерно равные части. Если в массиве нечетное
количество элементов, одна из этих «половинок» на один элемент больше другой.
Подмассивы снова и снова делятся на половины, пока вы не получите массивы, каждый
из которых содержит только один элемент.
Затем вы объединяете пары одноэлементных массивов в двухэлементные массивы,
сортируя их в процессе. Затем эти отсортированные пары объединяются в
четырехэлементные массивы и так далее, пока вы не получите отсортированный исходный
массив.
Есть два основных способа реализации алгоритма сортировки слиянием, один из которых
использует нисходящий подход, как в приведенном выше примере, который чаще всего
используется для сортировки слиянием.
Другой подход, то есть снизу вверх , работает в противоположном направлении, без
рекурсии (работает итеративно) - если в нашем массиве N элементов, мы делим его на N
подмассивов одного элемента и сортируем пары смежных одноэлементных массивов, затем
сортируем смежные пары двухэлементных массивов и т. д.

4.

• Если представить алгоритм по шагам, он будет выглядеть так:
1. Исходный массив: [4 2 5 1].
2. Делим пополам: [4 2] ←→ [5 1] (у нас появилось два новых массива, значит, к ним применяем тоже сортировку
слиянием).
3. Делим пополам первый массив: [4] ←→ [2].
4. Раз в каждом по одному элементу, то сортируем и склеиваем в один: [2 4].
5. Делим пополам второй массив: [5] ←→ [1].
6. Раз в каждом по одному элементу — сортируем и склеиваем в один: [1 5].
7. К нам вернулись два отсортированных подмассива, а значит, нам нужно их отсортировать и склеить в один.
8. Сравниваем первые элементы: 1 и 2. Единица меньше двух, значит, в итоговый массив записываем 1, и у нас
остаются два массива: [2 4] и [5].
9. Сравниваем первые элементы: 2 и 5. Двойка меньше пяти, значит, в итоговый массив записываем 2, и у нас
остаются два массива: [4] и [5].
10. Точно так же сравниваем первые элементы до тех пор, пока в обоих массивах не исчезнут все элементы. Как
только это произойдёт — массив отсортирован.

5.

Пример:
Пусть
наш
массив
разделён
примерно на две равные части,
причём
обе
части
уже
отсортированные!
Тогда
можно
легко
полностью отсортировать данны
й массив. Напишем функцию
слияния:

6.

Второй пример
сортировки слиянием
на конкретном
массиве.

7.

• Где может быть полезна?
Внешняя сортировка слиянием практична для запуска с использованием
дисков или ленточных накопителей, когда данные слишком большие, чтобы
поместиться в памяти. Внешняя сортировка объясняет, как сортировка
слиянием реализуется с дисковыми накопителями. Типичная сортировка
ленточных накопителей использует четыре ленточных накопителя. Все
операции ввода-вывода являются последовательными (за исключением
перемотки в конце каждого прохода). Минимальная реализация может
обойтись всего двумя буферами записи и несколькими программными
переменными.

8.

Спасибо За Ваше Внимание