Как реализовать сортировку слиянием в C ++ с примерами

Что такое сортировка слияния? Сортировка слиянием - это алгоритм сортировки на основе сравнения, который относится к категории «разделяй и властвуй». Сортировка слиянием используется для сортировки массива на основе стратегии «разделяй и властвуй», которая будет кратко рассмотрена в этом посте вместе с другими концепциями, такими как алгоритм с примером. Мы также рассмотрим временную сложность сортировки слиянием в C ++.

Следующие указатели будут рассмотрены в этой статье,

• Алгоритм разделяй и властвуй
• Понимание алгоритма сортировки слиянием на примере
• Псевдокод для сортировки слиянием
• Программа на C ++ для сортировки слиянием
• Временная сложность сортировки слиянием

Продолжаем эту статью о сортировке слиянием в C ++

Алгоритм разделяй и властвуй

Если вы уже знакомы с тем, как работает быстрая сортировка, возможно, вы знаете стратегию «разделяй и властвуй». «Разделяй и властвуй» состоит из трех основных шагов. Для понимания этих шагов давайте рассмотрим массив Hello [], имеющий начальный индекс «a» и конечный индекс «n», поэтому мы можем записать наш массив следующим образом Hello [a & hellip..n]

Разделяй - главный шаг или главный шаг «разделяй и властвуй» - это разделить данную проблему на подзадачи или части. Уловка здесь в том, что подзадачи должны быть похожи на исходную и меньше по размеру. В нашем случае мы разделим наш массив на 2 половины [a & hellip.m] [m + 1 & hellip..n] m лежит в середине индекса a и n

Победить - как только мы закончим разделение нашей проблемы на подзадачи. Мы решаем эти подзадачи рекурсивно.

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

Продолжаем эту статью о сортировке слиянием в C ++

Понимание алгоритма сортировки слиянием на примере

На данный момент мы знаем, какой подход будет использоваться при сортировке слиянием. Итак, давайте рассмотрим пример и пройдемся по каждому шагу от Hello [] без сортировки до отсортированного массива.
Пример - Здравствуйте [10, 3, 7, 1, 15, 14, 9, 22]

На изображении выше мы рассмотрели несортированный массив и использовали сортировку слиянием для получения отсортированного массива. Теперь давайте посмотрим на каждый шаг и поймем весь алгоритм

1. Сначала мы рассмотрели массив Hello [10, 3, 7, 1, 15, 14, 9, 22] в этом массиве всего 8 элементов.

2. Как мы видели ранее, сортировка слиянием использует подход «разделяй и властвуй» для сортировки элементов. Мы нашли m, который находится в середине нашего массива, и разделили наш массив от середины, где m = (a - n) / 2 'a' - это индекс самого левого элемента, а n - индекс самого правого элемента нашего массива. .

3. После первого деления у нас есть 2 части по 4 элемента каждая. Давайте посмотрим на первую половину [10, 3, 7, 1].

4. Разделим [10, 3, 7, 1] на 2 части [10, 3] и [7, 1]. После этого разделим их на [10], [3], [7], [1]. Дальнейшее деление невозможно, так как мы не можем вычислить m. список, содержащий единственный элемент, всегда считается отсортированным.

5. Как происходит слияние? Давай выясним. Сначала [10] и [3] сравниваются и объединяются в порядке возрастания [3, 10] таким же образом, как мы получаем [1, 7]

тип данных даты сервера sql

6. После этого сравниваем [3, 10] и [1, 7]. После сравнения мы объединяем их в порядке возрастания и получаем [1, 3, 7, 10].

7. [15, 14, 9, 2] также разделяется и объединяется аналогичным образом в форму [9, 14, 15, 22].

8. На последнем этапе мы сравниваем и объединяем [15, 14, 9, 2] [9, 14, 15, 22], чтобы получить наш отсортированный массив.то есть [1, 3, 7, 9, 10, 14, 15, 22].

Продолжаем эту статью о сортировке слиянием в C ++

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

Начать, если осталось
Функция mergeSort () рекурсивно вызывает себя, чтобы разделить наш массив, пока он не станет одним элементом, а функция merge () используется для объединения отсортированных массивов.
  Продолжаем эту статью о сортировке слиянием в C ++
 Программа сортировки слиянием на C ++ 
#include #include #include с использованием пространства имен std void merge (int a [], int Firstindex, int m, int Lastindex) // объединяет подмассивы, которые создаются при делении void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Привет [размер], я cout<<'Enter the elements of the array one by one:n' for(i=0 i>Привет [i] mergeSort (Привет, 0, размер - 1) cout<<'The Sorted List isn' for(i=0 i
 Вывод- 
Продолжаем эту статью о сортировке слиянием в C ++
 Сложность времени 
Сложность времени - важный аспект, который следует учитывать, когда мы говорим об алгоритмах. Считается, что сортировка слиянием имеет большую временную сложность по сравнению с другими алгоритмами сортировки.
Время работы в наихудшем случае - O (n log n) 
Лучшее время работы - O (n log n) 
Среднее время работы - O (n log n)
На этом мы подошли к концу этой статьи о сортировке слиянием в C ++. Если вы хотите узнать больше, ознакомьтесь с   от Edureka, надежной компании онлайн-обучения. Курс обучения и сертификации по Java J2EE и SOA от Edureka разработан, чтобы научить вас базовым и продвинутым концепциям Java, а также различным средам Java, таким как Hibernate и Spring.
 Есть вопрос к нам? Пожалуйста, укажите это в разделе комментариев этого блога, и мы свяжемся с вами как можно скорее.