Сортировка слияниями (алгоритм фон Неймана)
Метод основан на многократных слияниях уже упорядоченных групп элементов массива. В начале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждой. Слиянием соседних групп получают упорядоченные группы по два элемента (кроме, может быть, последней, если для неё не нашлось парной). Далее упорядоченные группы укрупняют тем же способом. Схематично это можно представить так (рисунок 15). Вначале происходит слияние групп по одному элементу. Образовались упорядоченные группы по 2 элемента. Далее процесс продолжается для укрупненных групп.
Рисунок 1. Пример сортировки фон Неймана
Задание. Для всех вариантов исходными данными являются одномерный массив, элементы которого задаются с помощью датчика случайных чисел от – 50 до +50. Варианты 1, 2, 3 4 и 5 используют сортировку простыми вставками, варианты 6, 7, 8, 9 и 10 сортировку обменами I, варианты 11, 12, 13, 14 и 15 – сортировку выбором, варианты 16, 17, 18, 19 и 20 – сортировку обменами II. Желающие получить повышенный балл могут использовать сортировку бинарными вставками, «быструю сортировку» или сортировку фон-Неймана.
Вариант 1, 6, 11, 16. Даны целые числа al,...,an. Получить в порядке возрастания различные числа из этого массива.
Вариант 2, 7, 12, 17. Даны целые числа al,...,an. Упорядочить массив по возрастанию. Удалить из массива элемент с номером k, затем вставить число b так, чтобы упорядоченность не нарушалась. Числа k и b вводятся с клавиатуры.
Вариант 3, 8, 13, 18. Даны целые числа al,...,an. Получить в порядке убывания различные числа из этого массива.
Вариант 4, 9, 14, 19. Даны целые числа al,...,an. Упорядочить массив по убыванию. Удалить из массива элемент с номером k, затем вставить число b так, чтобы упорядоченность не нарушалась. Числа k и b вводятся с клавиатуры.
Вариант 5, 10, 15, 20. В массиве al,...,an переставить числа таким образом, чтобы вначале шли элементы большие al, упорядоченные по возрастанию, затем сам элемент al, затем элементы меньшие al, упорядоченные по убыванию.