Построчное объяснение алгоритма сортировки слиянием в C ++
Автор кратко объяснил здесь сортировку слиянием с представлением диаграммы и скриншотами кода, а также некоторыми рекомендуемыми ссылками. Также построчное объяснение выполнения программы для этого алгоритма на C ++.
Сортировка слиянием - это алгоритм «разделяй и властвуй», основанный на идее разбиения списка на несколько подсписок до тех пор, пока каждый подсписок не будет состоять из одного элемента, и объединения этих подсписок таким образом, чтобы в результате получился отсортированный список.
Диаграмма, поясняющая работу алгоритма сортировки слиянием
Теперь давайте закодируем этот алгоритм
Строка 62 (рис. 1): - Здесь начинается наша программа, объявляющая массив с именем myarray из «5» и объявляющая целое число для хранения размера массива, равного « 5 ”с именем arr_size. Теперь просим пользователя ввести элементы для массива, а затем распечатать массив перед сортировкой.
Строка 76 (рис. 1): - Здесь мы вызываем функцию mergeSort для сортировки, передавая массив, крайний левый индекс и крайний правый индекс массива.
Теперь напишем код для функции mergeSort
Строка 48 (рис. 2): - Теперь в этой функции мы берем параметры, массив, крайний левый индекс и крайний правый индекс соответственно.
Строка 49 (рис. 2): - В этом случае мы проверяем, является ли крайний левый индекс массива, равный 0, меньше, чем крайний правый индекс (крайний правый индекс может быть любым числом, в зависимости от размер массива). Очевидно, что крайний левый индекс всегда стремится к нулю. Итак, цель проверки - убедиться, что в массиве более одного элемента или нет.
Строка 51 (рис. 2): - Здесь мы находим средний индекс массива, который нужно разделить и победить.
Перед тем, как перейти к следующему, вы должны хотя бы услышать о рекурсивных функциях, а если нет, то просто погуглите это для краткого обзора.
Строка 54 (рис. 2): - Здесь мы делим массив на левую часть, поэтому мы передаем параметры как массив, крайний левый и средний (который является крайним правым индексом для левой половины массив).
Строка 55 (рис. 2): - Здесь мы делим массив на правую часть, поэтому мы передаем параметры как массив, средний + 1 (который является крайним левым для правой половины массива) , право самое.
Строка 58 (рис. 2): - Здесь мы вызываем функцию merge для объединения массивов путем их сортировки. И передача аргументов в виде массива, крайний левый, средний, крайний правый.
ПРИМЕЧАНИЕ. - Чтобы понять рекурсию, происходящую в приведенном выше коде, я рекомендую вам посмотреть приведенное ниже видео с определенной продолжительности (с 11:30 до последнего).
Теперь давайте напишем код для функции слияния
Строка 4 (рис. 3): - В этой функции слияния мы передаем параметры как массив, крайний левый, крайний правый и средний. И инициализация некоторых целых чисел, таких как, i, который будет крайним левым индексом, j, который представляет начало правой части массива, и k, самым левым.
Строка 9 (рис. 3): - Создание временного массива для хранения отсортированных элементов.
Строка 10 (рис. 3): - Здесь мы даем два условия для запуска цикла while, первое - проверять, меньше ли крайний левый индекс среднего или равен среднему, а второе - проверять, j меньше или равно крайнему правому краю или нет.
Проверяя цикл while, мы делаем так, чтобы цикл оставался левой частью, как левая, а правая - правой. Затем сравниваем элементы для обмена.
И проделаем то же самое в следующих циклах while, чтобы сравнить левую часть с правой.
Строка 34 (рис. 3): - Сохранение отсортированного массива в arr для передачи в параметр.
Затем, как и в основной функции, мы печатаем после вызова функции сортировки слиянием.
Итак, все было о сортировке слиянием, о том, как она работает, и о объяснении.
