Algoritmo de fusión
Los algoritmos de combinación son una familia de algoritmos que toman múltiples listas ordenadas como entrada y producen una sola lista como salida, que contiene todos los elementos de las listas de entrada en orden ordenado. Estos algoritmos se utilizan como subrutinas en varios algoritmos de ordenación , el más famoso es la ordenación por fusión .
El algoritmo de combinación juega un papel fundamental en el algoritmo de clasificación de combinación , un algoritmo de clasificación basado en la comparación . Conceptualmente, el algoritmo de clasificación por fusión consta de dos pasos:
En la ilustración se proporciona un ejemplo de clasificación por combinación. Comienza con una matriz desordenada de 7 enteros. La matriz se divide en 7 particiones; cada partición contiene 1 elemento y está ordenada. Luego, las particiones ordenadas se fusionan para producir particiones ordenadas más grandes, hasta que queda 1 partición, la matriz ordenada.
La fusión de dos listas ordenadas en una se puede hacer en tiempo lineal y espacio lineal o constante (según el modelo de acceso a datos). El siguiente pseudocódigo demuestra un algoritmo que combina listas de entrada (ya sean listas enlazadas o matrices ) A y B en una nueva lista C. [1] [2] : 104 El encabezado de función produce el primer elemento de una lista; "soltar" un elemento significa eliminarlo de su lista, generalmente incrementando un puntero o índice.
Cuando las entradas son listas vinculadas, este algoritmo se puede implementar para usar solo una cantidad constante de espacio de trabajo; los punteros en los nodos de las listas se pueden reutilizar para la contabilidad y para construir la lista fusionada final.
En el algoritmo de ordenación por fusión, esta subrutina se usa normalmente para fusionar dos submatrices A[lo..mid] , A[mid+1..hi] de una única matriz A . Esto se puede hacer copiando los subconjuntos en un conjunto temporal y luego aplicando el algoritmo de combinación anterior. [1] Se puede evitar la asignación de una matriz temporal, pero a expensas de la velocidad y la facilidad de programación. Se han ideado varios algoritmos de combinación en el lugar, [3] a veces sacrificando el límite de tiempo lineal para producir un algoritmo O ( n log n ) ; [4] ver Merge sort § Variantes para discusión.
