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

Сортировка слияниемАлгоритм сортировки слиянием использует стратегию «разделяй и властвуй», в которой мы делим определенную задачу на подзадачи и решаем эти подзадачи по отдельности.

Затем эти подзадачи объединяются или сливаются вместе для формирования единого решения.

Сортировка слиянием выполняется с использованием следующих шагов:

1) Список для сортировки разбивается на два массива одинаковой длины, путем деления списка на элементы. Если количество элементов в списке равно 0 или 1, то список считается отсортированным.

2) Каждый подсписок сортируется индивидуально с помощью рекурсивной сортировки слиянием.

3) Отсортированные подсписки затем объединяются или сливаются вместе, чтобы сформировать полный отсортированный список.

Общий алгоритм

Шаг 1: Объявляем массив Arr длины N
Если N=1, Arr уже отсортирован
Если N>1, Left = 0, right = N-1
Шаг 2: Находим элемент = (левый + правый)/2
Шаг 3: Вызов merge_sort(Arr,left,middle) = >рекурсивно отсортировать первую половину
Шаг 4: Вызов merge_sort(Arr,middle+1,right) => рекурсивно отсортируйте вторую половину
Шаг 5: Вызов merge(Arr,left,middle,right) для объединения отсортированных массивов на вышеуказанных шагах.
Шаг 6: Вывод данных

Как показано в приведенном выше, в алгоритме сортировки слиянием мы делим массив на половину и сортируем каждую половину, используя рекурсивную сортировку слиянием. После того, как подмассивы отсортированы по отдельности, два подмассива объединяются вместе, чтобы сформировать полный отсортированный массив.

Псевдокод для сортировки слиянием

Ниже приведен псевдокод метода сортировки слиянием. Во-первых, у нас есть процедура сортировки слиянием, которая рекурсивно разбивает массив на половины. Затем, следует процедура слияния, которая объединит отсортированные меньшие массивы, чтобы получить полный отсортированный массив.

Давайте теперь продемонстрируем технику сортировки слиянием на примере.

Демонстрация техники сортировки слиянием

Приведенную выше демонстрацию можно показать в табличной форме:

Читать также:  Указатели и операции с указателями в C++

Проход Несортированный список Разделение Отсортированный список
1 {12, 23,2,43,51,35,19,4} {12,23,2,43}
{51,35,19,4}
{}
2 {12,23,2,43}
{51,35,19,4}
{12,23}{2,43}
{51,35}{19,4}
{}
3 {12,23}{2,43}
{51,35}{19,4}
{12,23} {2,43}
{35,51}{4,19}
{12,23} {2,43}
{35,51}{4,19}
4 {12,23} {2,43}
{35,51}{4,19}
{2,12,23,43}
{4,19,35,51}
{2,12,23,43}
{4,19,35,51}
5 {2,12,23,43}
{4,19,35,51}
{2,4,12,19,23,35,43,51} {2,4,12,19,23,35,43,51}
6 {} {} {2,4,12,19,23,35,43,51}

Как показано в приведенной выше демонстрации, сначала массив делится на два подмассива длины 4. Каждый подмассив далее делится еще на два подмассива длины 2. Затем каждый подмассив дополнительно делится на подмассив по одному элементу каждый. Весь этот процесс является процессом «Разделения».

После того, как мы разделили массив на подмассивы, состоящие из одного элемента в каждом, теперь нам нужно объединить эти массивы в отсортированном порядке.

Как показано выше, мы рассматриваем каждый подмассив одного элемента и сначала объединяем элементы, чтобы сформировать подмассивы из двух элементов в отсортированном порядке. Затем отсортированные подмассивы длины два сортируются и объединяются для формирования двух подмассивов длины четыре каждый. Затем мы объединяем эти два подмассива, чтобы сформировать полный отсортированный массив.

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

Алгоритм или метод сортировки слиянием, который мы предоставили выше, использует рекурсию. Его также называют «рекурсивной сортировкой слиянием».

Вы уже знаете, что рекурсивные функции используют стек вызовов функций для хранения промежуточного состояния вызывающей функции. Он также хранит другую учетную информацию для параметров и т. д. и создает проблемы с точки зрения хранения записи активации вызова функции, а также возобновления выполнения.

От всех этих проблем можно избавиться, если использовать итерационные функции вместо рекурсивных. Приведенный выше алгоритм сортировки слиянием также можно легко преобразовать в итерационные шаги с использованием циклов и принятия решений.

Читать также:  Абстракция данных в C++

Как и рекурсивная сортировка слиянием, итеративная сортировка слиянием также имеет сложность O (nlogn), следовательно, с точки зрения производительности они работают на одном уровне друг с другом.

В этой статье мы сосредоточимся на рекурсивной сортировке слиянием, а затем реализуем рекурсивную сортировку слиянием с использованием языков C++ и Java.

Ниже приведена реализация метода сортировки слиянием с использованием C++:

Вывод данных:

Введите количество элементов для сортировки: 10
Введите 10 элементов для сортировки: 101 10 2 43 12 54 34 64 89 76
Отсортированный массив
2 10 12 34 43 54 64 76 89 101

В этой программе мы определили две функции: merge_sort и merge . В функции merge_sort мы делим массив на два равных массива и вызываем функцию слияния для каждого из этих подмассивов. В функции слияния мы выполняем фактическую сортировку этих подмассивов, а затем объединяем их в один полный отсортированный массив.

Далее мы реализуем технику сортировки слиянием на языке Java:

Вывод данных:

Входной массив
101 10 2 43 12 54 34 64 89 76
Массив, отсортированный с использованием сортировки слиянием
2 10 12 34 43 54 64 76 89 101

В реализации на Java мы также используем ту же логику, что и в реализации на C++.

Сортировка слиянием — это эффективный способ сортировки списков, который в основном используется для сортировки связных списков. Поскольку в нем используется подход «разделяй и властвуй», метод сортировки слиянием одинаково эффективен как для маленьких, так и для больших массивов.

Читать также:  Разработка графического интерфейса для робота с использованием Qt и Python

Анализ сложности алгоритма сортировки слиянием

Вы знаете, что для того, чтобы выполнить сортировку методом слияния, мы сначала делим массив на две равные половины. Это представлено «log n», который является логарифмической функцией, а количество предпринятых шагов равно log (n+1).

Далее, чтобы найти средний элемент массива, нам требуется один шаг, т.е. O (1).

Затем, чтобы объединить подмассивы в массив из n элементов, нам потребуется O (n) времени выполнения.

Таким образом, общее время выполнения сортировки слиянием будет равно n (log n+1), что дает нам временную сложность O (n*logn).

Временная сложность в худшем случае O(n*log n)
Временная сложность в лучшем случае O(n*log n)
Средняя временная сложность O(n*log n)
Пространственная сложность O(n)

Временная сложность для сортировки слиянием одинакова во всех трех случаях (наихудший, лучший и средний), поскольку она всегда делит массив на подмассивы, а затем объединяет подмассивы за линейное время.

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

Итог

Сортировка слиянием использует стратегию «разделяй и властвуй», которая делит массив или список на многочисленные вложенные массивы и сортирует их по отдельности, а затем объединяет в полный отсортированный массив.

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

В нашей следующей статье мы поговорим о быстрой сортировке в C++.

С Уважением, МониторБанк

Добавить комментарий