Алгоритм сортировки слиянием использует стратегию «разделяй и властвуй», в которой мы делим определенную задачу на подзадачи и решаем эти подзадачи по отдельности.
Затем эти подзадачи объединяются или сливаются вместе для формирования единого решения.
Сортировка слиянием выполняется с использованием следующих шагов:
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: Вывод данных
Как показано в приведенном выше, в алгоритме сортировки слиянием мы делим массив на половину и сортируем каждую половину, используя рекурсивную сортировку слиянием. После того, как подмассивы отсортированы по отдельности, два подмассива объединяются вместе, чтобы сформировать полный отсортированный массив.
Псевдокод для сортировки слиянием
Ниже приведен псевдокод метода сортировки слиянием. Во-первых, у нас есть процедура сортировки слиянием, которая рекурсивно разбивает массив на половины. Затем, следует процедура слияния, которая объединит отсортированные меньшие массивы, чтобы получить полный отсортированный массив.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a[0] ... a[N/2] var array2 as array = a[N/2+1] ... a[N] array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1[0] > array2[0] ) add array2 [0] to the end of c remove array2 [0] from array2 else add array1 [0] to the end of c remove array1 [0] from array1 end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure |
Давайте теперь продемонстрируем технику сортировки слиянием на примере.
Приведенную выше демонстрацию можно показать в табличной форме:
| Проход | Несортированный список | Разделение | Отсортированный список |
| 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. Затем каждый подмассив дополнительно делится на подмассив по одному элементу каждый. Весь этот процесс является процессом «Разделения».
После того, как мы разделили массив на подмассивы, состоящие из одного элемента в каждом, теперь нам нужно объединить эти массивы в отсортированном порядке.
Как показано выше, мы рассматриваем каждый подмассив одного элемента и сначала объединяем элементы, чтобы сформировать подмассивы из двух элементов в отсортированном порядке. Затем отсортированные подмассивы длины два сортируются и объединяются для формирования двух подмассивов длины четыре каждый. Затем мы объединяем эти два подмассива, чтобы сформировать полный отсортированный массив.
Итеративная сортировка слиянием
Алгоритм или метод сортировки слиянием, который мы предоставили выше, использует рекурсию. Его также называют «рекурсивной сортировкой слиянием».
Вы уже знаете, что рекурсивные функции используют стек вызовов функций для хранения промежуточного состояния вызывающей функции. Он также хранит другую учетную информацию для параметров и т. д. и создает проблемы с точки зрения хранения записи активации вызова функции, а также возобновления выполнения.
От всех этих проблем можно избавиться, если использовать итерационные функции вместо рекурсивных. Приведенный выше алгоритм сортировки слиянием также можно легко преобразовать в итерационные шаги с использованием циклов и принятия решений.
Как и рекурсивная сортировка слиянием, итеративная сортировка слиянием также имеет сложность O (nlogn), следовательно, с точки зрения производительности они работают на одном уровне друг с другом.
В этой статье мы сосредоточимся на рекурсивной сортировке слиянием, а затем реализуем рекурсивную сортировку слиянием с использованием языков C++ и Java.
Ниже приведена реализация метода сортировки слиянием с использованием C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low < high){ //разделим массив посередине и отсортируем независимо, используя сортировку слиянием mid=(low+high)/2; merge_sort(arr,low,mid); merge_sort(arr,mid+1,high); //объединим отсортированные массивы merge(arr,low,high,mid); } } // Сортировка слиянием void merge(int *arr, int low, int high, int mid) { int i, j, k, c[50]; i = low; k = low; j = mid + 1; while (i <= mid && j <= high) { if (arr[i] < arr[j]) { c[k] = arr[i]; k++; i++; } else { c[k] = arr[j]; k++; j++; } } while (i <= mid) { c[k] = arr[i]; k++; i++; } while (j <= high) { c[k] = arr[j]; k++; j++; } for (i = low; i < k; i++) { arr[i] = c[i]; } } // считывание входного массива и вызов mergesort int main() { int myarray[30], num; cout<<"Enter number of elements to be sorted:"; cin>>num; cout<<"Enter "<<num<<" elements to be sorted:"; for (int i = 0; i < num; i++) { cin>>myarray[i]; } merge_sort(myarray, 0, num-1); cout<<"Sorted array\n"; for (int i = 0; i < num; i++) { cout<<myarray[i]<<"\t"; } } |
Вывод данных:
| Введите количество элементов для сортировки: 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
class MergeSort { void merge(int arr[], int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr[] = new int [left]; int Right_arr[] = new int [right]; for (int i=0; i<left; ++i) Left_arr[i] = arr[beg + i]; for (int j=0; j<right; ++j) Right_arr[j] = arr[mid + 1+ j]; int i = 0, j = 0; int k = beg; while (i<left&&j<right){ if (Left_arr[i] <= Right_arr[j]) { arr[k] = Left_arr[i]; i++; } else{ arr[k] = Right_arr[j]; j++; } k++; } while (i<left) { arr[k] = Left_arr[i]; i++; k++; } while (j<right){ arr[k] = Right_arr[j]; j++;k++; } } void merge_sort(int arr[], int beg, int end) { if (beg<end) { int mid = (beg+end)/2; merge_sort(arr, beg, mid); merge_sort(arr , mid+1, end); merge(arr, beg, mid, end); } } } class Main{ public static void main(String args[]) { int arr[] = {101,10,2,43,12,54,34,64,89,76}; System.out.println("\nInput Array"); for(int i =0; i<arr.length;i++) { System.out.print(arr[i]+" "); } MergeSort ob = new MergeSort(); ob.merge_sort(arr, 0, arr.length-1); System.out.println("\nArray sorted using merge sort"); for(int i =0; i<arr.length;i++) { System.out.print(arr[i]+" "); } } } |
Вывод данных:
| Входной массив 101 10 2 43 12 54 34 64 89 76 Массив, отсортированный с использованием сортировки слиянием 2 10 12 34 43 54 64 76 89 101 |
В реализации на Java мы также используем ту же логику, что и в реализации на C++.
Сортировка слиянием — это эффективный способ сортировки списков, который в основном используется для сортировки связных списков. Поскольку в нем используется подход «разделяй и властвуй», метод сортировки слиянием одинаково эффективен как для маленьких, так и для больших массивов.
Анализ сложности алгоритма сортировки слиянием
Вы знаете, что для того, чтобы выполнить сортировку методом слияния, мы сначала делим массив на две равные половины. Это представлено «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++.
С Уважением, МониторБанк