Neste tutorial, você aprenderá sobre a classificação por mesclagem. Além disso, você encontrará exemplos funcionais de merge sort C, C ++, Java e Python.
Merge Sort é um dos algoritmos de classificação mais populares, baseado no princípio do Algoritmo Divide and Conquer.
Aqui, um problema é dividido em vários subproblemas. Cada subproblema é resolvido individualmente. Finalmente, os subproblemas são combinados para formar a solução final.
Exemplo de mesclagem de classificação
Estratégia de divisão e conquista
Usando a técnica Divide and Conquer , dividimos um problema em subproblemas. Quando a solução para cada subproblema está pronta, 'combinamos' os resultados dos subproblemas para resolver o problema principal.
Suponha que tenhamos que classificar um array A. Um subproblema seria classificar uma subseção desse array começando no índice pe terminando no índice r, denotado como A (p… r).
Divide
Se q for o ponto intermediário entre p e r, então podemos dividir o submatriz A (p… r) em dois arrays A (p… q) e A (q + 1, r).
Conquistar
Na etapa de conquista, tentamos classificar os subarrays A (p … q) e A (q + 1, r). Se ainda não alcançamos o caso base, dividimos novamente esses dois subarrays e tentamos classificá-los.
Combinar
Quando a etapa de conquista atinge a etapa de base e obtemos duas submatrizes ordenadas A (p… q) e A (q + 1, r) para a matriz A (p… r), combinamos os resultados criando uma matriz ordenada A ( p… r) de dois subarrays classificados A (p… q) e A (q + 1, r).
O Algoritmo MergeSort
A função MergeSort divide repetidamente o array em duas metades até chegarmos a um estágio onde tentamos realizar MergeSort em um subarray de tamanho 1, ou seja, p == r.
Depois disso, a função de mesclagem entra em ação e combina os arrays classificados em arrays maiores até que todo o array seja mesclado.
MergeSort (A, p, r): se p> r retornar q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) mesclar (A, p, q, r )
Para classificar uma matriz inteira, precisamos chamar MergeSort(A, 0, length(A)-1).
Conforme mostrado na imagem abaixo, o algoritmo de classificação por mesclagem divide recursivamente a matriz em metades até chegarmos ao caso base da matriz com 1 elemento. Depois disso, a função de mesclagem seleciona os submatrizes classificados e os mescla para classificar gradualmente o array inteiro.
Mesclar classificação em ação
A intercalação Passo de Merge Sort
Cada algoritmo recursivo depende de um caso base e da capacidade de combinar os resultados dos casos base. A classificação de mesclagem não é diferente. A parte mais importante do algoritmo de classificação por mesclagem é, você adivinhou, a etapa de mesclagem.
A etapa de mesclagem é a solução para o problema simples de mesclar duas listas ordenadas (arrays) para construir uma grande lista ordenada (array).
O algoritmo mantém três ponteiros, um para cada uma das duas matrizes e um para manter o índice atual da matriz ordenada final.
Chegamos ao final de qualquer uma das matrizes? Não: Compare os elementos atuais de ambas as matrizes Copie o elemento menor na matriz classificada Mova o ponteiro do elemento contendo o elemento menor Sim: Copie todos os elementos restantes da matriz não vazia
Etapa de fusão
Escrevendo o Código para o Algoritmo de Mesclagem
Uma diferença perceptível entre a etapa de mesclagem que descrevemos acima e aquela que usamos para ordenar por mesclagem é que só executamos a função de mesclagem em submatrizes consecutivas.
É por isso que precisamos apenas do array, a primeira posição, o último índice do primeiro subarray (podemos calcular o primeiro índice do segundo subarray) e o último índice do segundo subarray.
Nossa tarefa é mesclar dois subarranjos A (p… q) e A (q + 1… r) para criar um array ordenado A (p… r). Portanto, as entradas para a função são A, p, q e r
A função de mesclagem funciona da seguinte maneira:
- Crie cópias dos subarrays
L ← A(p… q)e M ← A (q + 1… r). - Crie três ponteiros i, j e k
- i mantém o índice atual de L, começando em 1
- j mantém o índice atual de M, começando em 1
- k mantém o índice atual de A (p… q), começando em p.
- Até chegarmos ao final de L ou M, escolha o maior entre os elementos de L e M e coloque-os na posição correta em A (p … q)
- Quando ficarmos sem elementos em L ou M, pegue os elementos restantes e coloque em A (p … q)
No código, seria semelhante a:
// 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++; ) )
Função Merge () explicada passo a passo
Muita coisa está acontecendo nesta função, então vamos dar um exemplo para ver como isso funcionaria.
Como sempre, uma imagem vale mais que mil palavras.
Mesclando duas submatrizes consecutivas da matriz
O array A (0… 5) contém dois subarrays classificados A (0… 3) e A (4… 5). Vamos ver como a função de mesclagem mesclará os dois arrays.
void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)
Etapa 1: criar cópias duplicadas de submatrizes a serem classificadas
// 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) 
Crie cópias de subarrays para mesclar
Etapa 2: Manter o índice atual de submatrizes e matriz principal
int i, j, k; i = 0; j = 0; k = p; 
Manter índices de cópias de submatriz e matriz principal
Etapa 3: até chegarmos ao final de L ou M, escolha um elemento maior entre L e M e coloque-os na posição correta em 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++; ) 
Comparando elementos individuais de submatrizes classificados até chegarmos ao fim de um
Etapa 4: quando ficarmos sem elementos em L ou M, pegue os elementos restantes e coloque A (p … r)
// We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; ) 
Copie os elementos restantes do primeiro array para o subarray principal
// We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) ) 
Copie os elementos restantes da segunda matriz para a subarray principal
Esta etapa teria sido necessária se o tamanho de M fosse maior que L.
No final da função de mesclagem, o subarray A (p… r) é classificado.
Exemplos de Python, Java e 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; )
Mesclar complexidade de classificação
Complexidade de tempo
Melhor caso de complexidade: O (n * log n)
Pior caso de complexidade: O (n * log n)
Complexidade média do caso: O (n * log n)
Complexidade do Espaço
A complexidade do espaço de merge sort é O (n).
Mesclar aplicativos de classificação
- Problema de contagem de inversão
- Classificação externa
- Aplicativos de comércio eletrônico
