En el último artículo, nos familiarizamos con los tipos de fusión de relictos (causando principalmente interés histórico). ¿Cuál es la tendencia hoy?

Para familiarizarse con el concepto de ordenar a través de fusiones, generalmente se utilizan algoritmos de fusión equilibrados. El término "equilibrio" significa que el algoritmo divide recursivamente el conjunto y sus subconjuntos en partes aproximadamente iguales. Hoy nos fijamos en cómo se ve en la práctica.

Un par de funciones es igual para ambos métodos. De todos modos, ese "down-up", ese "up-down" es casi el mismo algoritmo, solo se muestra desde diferentes ángulos.

Necesitamos, de hecho, la fusión de dos mitades del segmento en una submatriz. Las mitades se ordenan simultáneamente en una matriz, se comparan los elementos actuales en ambas iteraciones y el elemento más pequeño entra en la 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++; } } } 

Copiar un segmento de una matriz a otra. Ambas implementaciones operan en dos matrices, los datos tienen que ser constantemente conducidos desde el principal al auxiliar y viceversa:

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

Fusión equilibrada descendente

Primero, se toma toda la matriz, después de lo cual comienza un descenso recursivo. Una matriz se dicotomiza hasta que alcanzamos las submatrices de un elemento (que se ordenan por sí mismas). Luego, la recursión comienza el aumento inverso, fusionando las submatrices a lo largo del camino (cuyo tamaño se duplica en cada nivel).

 //  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); } 

Fusión ascendente equilibrada

Aquí se realiza la iteración sobre la matriz, en el camino primero tomamos las matrices mínimas vecinas (de un elemento) y las fusionamos en pares. Habiendo duplicado las submatrices ordenadas en cada paso, fusionamos los vecinos nuevamente y continuamos hasta que obtengamos toda la matriz en la forma ordenada en la salida.

 //  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 } } 

En general, es preferible una implementación de arriba hacia abajo, ya que utiliza dos matrices de manera más eficiente, que simplemente cambian constantemente los roles de "principal / auxiliar". En la versión anterior, la matriz A siempre es primaria y la matriz B siempre es auxiliar. Como resultado, después de cada iteración, los datos de B deben devolverse en su totalidad a A, lo que no contribuye a la mejora de la complejidad algorítmica. Por otro lado, la implementación del ascendente es más simple; ni siquiera tiene recursividad.

Fusión desequilibrada

De la palabra "equilibrio" en sí mismo, arroja algún tipo de fiabilidad, estabilidad. Incluso puede tener la impresión de que un buen algoritmo debe estar equilibrado. Y el "desequilibrio" se asocia con algún tipo de temblores y distorsiones. Bueno, realmente, ¿no debería ser mejor uno equilibrado en todos los aspectos que uno no equilibrado ?

De hecho, es peor. Por supuesto, dividir las submatrices en mitades iguales (que es lo que se entiende por equilibrio para los tipos de fusión) es mucho más fácil de implementar. Divídase la matriz por la mitad y aplique la recursividad a cada mitad. En realidad, esta facilidad es la principal ventaja de una fusión equilibrada antes de una desequilibrada.

En las siguientes publicaciones, veremos los métodos desequilibrados. Son notablemente más difíciles de entender e implementar. Los datos para la fusión posterior no se distribuirán de manera uniforme y uniforme entre las matrices auxiliares, sino de acuerdo con una serie de números de Fibonacci generalizados. Y esto le permitirá lograr resultados poderosos que son inalcanzables para métodos equilibrados simplificados.

Referencias

Fusionar ( Google-translate ), Fusionar

Artículos de la serie:

• Aplicación Excel AlgoLab.xlsm
• Clases de intercambio
• Clases de inserción
• Ordenar por selección
• Combinar clasificaciones
  
  • Fusión equilibrada de arriba hacia abajo y de abajo hacia arriba
  • Orden de fusión multifase
  • Ordenar fusión en cascada
  • Orden de fusión oscilante
  • Clasificaciones roscadas e inmiscibles
  • Combinar clasificación de clasificación
• Ordenar por distribución
• Clasificación híbrida

Las siguientes clasificaciones de fusión ahora están disponibles en la aplicación AlgoLab (para aquellos que estudian algoritmos usando esta aplicación Excel, actualice el archivo).

Las matrices están temporalmente limitadas: su tamaño debe ser una potencia de dos (debido a algunas dificultades encontradas al programar la visualización). Un poco más tarde, será posible ordenar cualquier matriz.

Este artículo fue escrito con el apoyo de EDISON Software, una compañía que utiliza servicios en la nube para crear software embebido y desarrollar aplicaciones móviles en JAVA .