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

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

Сортировка слиянием - один из самых популярных алгоритмов сортировки, основанный на принципе алгоритма «разделяй и властвуй».

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

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

Стратегия разделяй и властвуй

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

Предположим, нам нужно отсортировать массив A. Подзадача будет заключаться в том, чтобы отсортировать подраздел этого массива, начиная с индекса p и заканчивая индексом r, обозначенный как A (p… r).

Разделить
Если q является средней точкой между p и r, то мы можем разделить подмассив A (p… r) на два массива A (p… q) и A (q + 1, r).

Завоевание
На этапе завоевания мы пытаемся отсортировать оба подмассива A (p… q) и A (q + 1, r). Если мы еще не достигли базового случая, мы снова разделяем оба этих подмассива и пытаемся отсортировать их.

Комбинирование
Когда шаг завоевания достигает базового шага и мы получаем два отсортированных подмассива A (p… q) и A (q + 1, r) для массива A (p… r), мы объединяем результаты, создавая отсортированный массив A ( p… r) из двух отсортированных подмассивов A (p… q) и A (q + 1, r).

Алгоритм MergeSort

Функция MergeSort многократно делит массив на две половины, пока мы не дойдем до стадии, на которой мы пытаемся выполнить MergeSort на подмассиве размером 1, то есть p == r.

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

 MergeSort (A, p, r): если p> r вернуть q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r )

Чтобы отсортировать весь массив, нам нужно вызвать MergeSort(A, 0, length(A)-1).

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

Сортировка слиянием в действии

Слияния Шаг Merge Sort

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

Шаг слияния - это решение простой проблемы слияния двух отсортированных списков (массивов) для создания одного большого отсортированного списка (массива).

Алгоритм поддерживает три указателя, по одному для каждого из двух массивов и один для поддержания текущего индекса окончательного отсортированного массива.

Достигли ли мы конца любого из массивов? Нет: сравнить текущие элементы обоих массивов. Копировать меньший элемент в отсортированный массив. Переместить указатель элемента, содержащего меньший элемент. Да: скопировать все оставшиеся элементы непустого массива.
Шаг слияния

Написание кода для алгоритма слияния

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

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

Наша задача - объединить два подмассива A (p… q) и A (q + 1… r), чтобы создать отсортированный массив A (p… r). Таким образом, входными параметрами функции являются A, p, q и r.

Функция слияния работает следующим образом:

  1. Создайте копии подмассивов L ← A(p… q)и M ← A (q + 1… r).
  2. Создайте три указателя i, j и k
    1. я поддерживает текущий индекс L, начиная с 1
    2. j поддерживает текущий индекс M, начиная с 1
    3. k поддерживает текущий индекс A (p… q), начиная с p.
  3. Пока мы не дойдем до конца L или M, выберите больший среди элементов из L и M и поместите их в правильное положение в A (p… q)
  4. Когда у нас заканчиваются элементы в L или M, возьмите оставшиеся элементы и поместите в A (p… q)

В коде это будет выглядеть так:

 // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )

Пошаговое объяснение функции Merge ()

В этой функции много чего происходит, поэтому давайте рассмотрим пример, чтобы увидеть, как это будет работать.

Как обычно, картинка говорит тысячу слов.

Объединение двух последовательных подмассивов массива

Массив A (0… 5) содержит два отсортированных подмассива A (0… 3) и A (4… 5). Давайте посмотрим, как функция слияния объединит два массива.

 void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)

Шаг 1. Создайте повторяющиеся копии подмассивов для сортировки

  // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9)
Создавать копии подмассивов для слияния

Шаг 2: Поддерживайте текущий индекс подмассивов и основного массива

  int i, j, k; i = 0; j = 0; k = p;
Поддерживать индексы копий подмассива и основного массива

Шаг 3: пока мы не дойдем до конца L или M, выберите больший из элементов L и M и поместите их в правильное положение в A (p… r)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Сравнивая отдельные элементы отсортированных подмассивов, пока не дойдем до конца одного

Шаг 4: Когда у нас заканчиваются элементы в L или M, возьмите оставшиеся элементы и вставьте A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Скопируйте оставшиеся элементы из первого массива в основной подмассив 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Скопируйте оставшиеся элементы второго массива в основной подмассив

Этот шаг был бы необходим, если бы размер M был больше L.

В конце функции слияния подмассив A (p… r) сортируется.

Примеры Python, Java и C / C ++

Python Java C C ++ 
 # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array) 
 // Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
 // Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
 // Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )

Сложность сортировки слиянием

Сложность времени

Наилучшая сложность случая: O (n * log n)

Наихудшая сложность: O (n * log n)

Средняя сложность кейса: O (n * log n)

Космическая сложность

Пространственная сложность сортировки слиянием - O (n).

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

  • Проблема счетчика инверсий
  • Внешняя сортировка
  • Приложения электронной коммерции

Интересные статьи...

Рекомендуем