No último artigo, nos familiarizamos com tipos de mesclagem de relíquias (causando principalmente interesse histórico). Qual é a tendência hoje?

Para se familiarizar com o conceito de pedido por meio de fusões, geralmente são usados ​​algoritmos de mesclagem balanceada. O termo "equilíbrio" significa que o algoritmo divide recursivamente a matriz e seus sub-arranjos em partes aproximadamente iguais. Hoje, olhamos como fica na prática.

Um par de funções é o mesmo para os dois métodos. Enfim, esse "down-up", esse "up-down" é quase o mesmo algoritmo, apenas mostrado sob diferentes ângulos.

Precisamos, de fato, da fusão de duas metades do segmento em um subarray. As metades são classificadas simultaneamente em uma matriz, os elementos atuais em ambas as iterações são comparados e o elemento menor entra na segunda matriz:

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } } 

Copiando um segmento de uma matriz para outra. Ambas as implementações operam em duas matrizes, os dados precisam ser constantemente direcionados do principal para o auxiliar e vice-versa:

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; } 

Fusão equilibrada descendente

Primeiro, a matriz inteira é obtida, após o que uma descida recursiva começa. Uma matriz é dicotomizada até atingirmos os sub-arranjos de um elemento (que são classificados por eles mesmos). Em seguida, a recursão inicia a subida inversa, mesclando os subarrays ao longo do caminho (cujo tamanho dobra em cada nível).

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); } 

Fusão ascendente equilibrada

Aqui a iteração sobre a matriz ocorre, ao longo do caminho, primeiro pegamos as matrizes mínimas vizinhas (de um elemento) e as fundimos em pares. Depois de duplicar as sub-matrizes classificadas em cada etapa, mesclamos os vizinhos novamente e continuamos até obtermos toda a matriz na forma classificada na saída.

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } } 

Em geral, é preferível uma implementação de cima para baixo, pois utiliza duas matrizes com mais eficiência, que simplesmente alteram constantemente os papéis de "principal / auxiliar". Na versão upstream, a matriz A é sempre primária e a matriz B é sempre auxiliar. Como resultado, após cada iteração, os dados de B devem ser retornados na íntegra para A, o que não contribui para a melhoria da complexidade algorítmica. Por outro lado, a implementação do ascendente é mais simples, nem sequer tem recursão.

Fusão desequilibrada

Da própria palavra "equilíbrio", sopra algum tipo de confiabilidade, estabilidade. Você pode até ter a impressão de que um bom algoritmo deve ser equilibrado. E o “desequilíbrio” está associado a algum tipo de tremor e distorção. Bem, realmente, um equilibrado não deveria ser melhor em todos os aspectos do que um desequilibrado ?

De fato, é pior. Evidentemente, é muito mais fácil implementar a divisão de sub-matrizes em metades iguais (que é o que se entende por equilíbrio para tipos de mesclagem). Divida a matriz ao meio e aplique recursão a cada metade. Na verdade, essa facilidade é a principal vantagem de uma fusão equilibrada antes de uma desequilibrada.

Nas publicações a seguir, veremos métodos desequilibrados. Eles são visivelmente mais difíceis de entender e implementar. Os dados para mesclagem subsequente não serão distribuídos de maneira uniforme e uniforme entre matrizes auxiliares, mas de acordo com vários números generalizados de Fibonacci. E isso permitirá que você obtenha resultados poderosos que são inatingíveis para métodos equilibrados simplificados.

Referências

Mesclar ( tradução do Google ), Mesclar

Artigos da série:

• Aplicativo Excel AlgoLab.xlsm
• Classificações de Câmbio
• Classificações de inserção
• Classificar por seleção
• Mesclar classificações
  
  • Fusão equilibrada de cima para baixo e de baixo para cima
  • Classificação de mesclagem multifásica
  • Classificação de mesclagem em cascata
  • Classificação de mesclagem oscilante
  • Classificações roscadas e imiscíveis
  • Comparação de Mesclagem
• Classificar por distribuição
• Classificação híbrida

As próximas classificações de mesclagem estão agora disponíveis no aplicativo AlgoLab (para quem estuda algoritmos usando esse aplicativo do Excel, atualize o arquivo).

As matrizes são temporariamente limitadas - seu tamanho deve ser um poder de dois (devido a algumas dificuldades encontradas ao programar a visualização). Um pouco mais tarde, será possível classificar qualquer matriz.

Este artigo foi escrito com o suporte da EDISON Software, uma empresa que usa serviços em nuvem para criar software incorporado e desenvolver aplicativos móveis em JAVA .