Ordenación por fusión e inserción

Tipo de algoritmo de ordenación por comparación

En informática , el algoritmo de ordenación por inserción-merge o Ford–Johnson es un algoritmo de ordenación por comparación publicado en 1959 por LR Ford Jr. y Selmer M. Johnson . ^{[1] [2] [3] [4]} Utiliza menos comparaciones en el peor de los casos que los mejores algoritmos conocidos anteriormente, el ordenamiento por inserción binario y el ordenamiento por combinación , ^[1] y durante 20 años fue el algoritmo de ordenación con menos comparaciones conocidas. ^[5] Aunque no tiene importancia práctica, sigue siendo de interés teórico en relación con el problema de la ordenación con un número mínimo de comparaciones. ^[3] El mismo algoritmo también puede haber sido descubierto de forma independiente por Stanisław Trybuła y Czen Ping. ^[4]

Algoritmo

La ordenación por fusión-inserción realiza los siguientes pasos, sobre una entrada de elementos: ^[6] ${\displaystyle X}$ ${\displaystyle n}$

1. Agrupe los elementos en pares de elementos, arbitrariamente, dejando un elemento sin aparear si hay un número impar de elementos. ${\displaystyle X}$ ${\displaystyle \lfloor n/2\rfloor }$
2. Realice comparaciones, una por par, para determinar el mayor de los dos elementos en cada par. ${\displaystyle \lfloor n/2\rfloor }$
3. Ordene de forma recursiva los elementos más grandes de cada par, creando una secuencia ordenada de los elementos de entrada, en orden ascendente, utilizando la ordenación por fusión-inserción. ${\displaystyle \lfloor n/2\rfloor }$ ${\displaystyle S}$ ${\displaystyle \lfloor n/2\rfloor }$
4. Insertar al inicio del elemento que se emparejó con el primer y más pequeño elemento de . ${\displaystyle S}$ ${\displaystyle S}$
5. Inserte los elementos restantes de en , uno a la vez, con un orden de inserción especialmente elegido que se describe a continuación. Utilice la búsqueda binaria en subsecuencias de (como se describe a continuación) para determinar la posición en la que se debe insertar cada elemento. ${\displaystyle \lceil n/2\rceil -1}$ ${\displaystyle X\setminus S}$ ${\displaystyle S}$ ${\displaystyle S}$

El algoritmo está diseñado para aprovechar el hecho de que las búsquedas binarias utilizadas para insertar elementos son más eficientes (desde el punto de vista del análisis del peor caso) cuando la longitud de la subsecuencia que se busca es uno menos que una potencia de dos . Esto se debe a que, para esas longitudes, todos los resultados de la búsqueda utilizan el mismo número de comparaciones entre sí. ^[1] Para elegir un orden de inserción que produzca estas longitudes, considere la secuencia ordenada después del paso 4 del esquema anterior (antes de insertar los elementos restantes), y sea el elemento n de esta secuencia ordenada. Por lo tanto, ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$

${\displaystyle S=(x_{1},x_{2},x_{3},\dots ),}$

donde cada elemento con se empareja con un elemento que aún no se ha insertado. (No hay elementos o porque y se emparejaron entre sí). Si es impar, el elemento no emparejado restante también debe numerarse como con mayor que los índices de los elementos emparejados. Luego, el paso final del esquema anterior se puede expandir a los siguientes pasos: ^{[1] [2] [3] [4]} ${\displaystyle x_{i}}$ ${\displaystyle i\geq 3}$ ${\displaystyle y_{i}<x_{i}}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle n}$ ${\displaystyle y_{i}}$ ${\displaystyle i}$

• Divida los elementos no insertados en grupos con índices contiguos. Hay dos elementos y en el primer grupo, y las sumas de los tamaños de cada dos grupos adyacentes forman una secuencia de potencias de dos. Por lo tanto, los tamaños de los grupos son: 2, 2, 6, 10, 22, 42, ... ${\displaystyle y_{i}}$ ${\displaystyle y_{3}}$ ${\displaystyle y_{4}}$
• Ordene los elementos no insertados por sus grupos (índices menores a índices mayores), pero dentro de cada grupo ordénelos de índices mayores a índices menores. De esta manera, el orden se convierte en

${\displaystyle y_{4},y_{3},y_{6},y_{5},y_{12},y_{11},y_{10},y_{9},y_{8},y_{7},y_{22},y_{21}\dots }$

• Utilice este orden para insertar los elementos en . Para cada elemento , utilice una búsqueda binaria desde el inicio de hasta , pero sin incluirlo, para determinar dónde insertar . ${\displaystyle y_{i}}$ ${\displaystyle S}$ ${\displaystyle y_{i}}$ ${\displaystyle S}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

Análisis

Sea el número de comparaciones que realiza la ordenación por inserción y fusión, en el peor de los casos, al ordenar elementos. Este número de comparaciones se puede desglosar como la suma de tres términos: ${\displaystyle C(n)}$ ${\displaystyle n}$

• ${\displaystyle \lfloor n/2\rfloor }$comparaciones entre los pares de elementos,
• ${\displaystyle C(\lfloor n/2\rfloor )}$comparaciones para la llamada recursiva, y
• un cierto número de comparaciones para las inserciones binarias utilizadas para insertar los elementos restantes.

En el tercer término, el número de comparaciones en el peor de los casos para los elementos del primer grupo es dos, porque cada uno se inserta en una subsecuencia de de longitud como máximo tres. Primero, se inserta en la subsecuencia de tres elementos . Luego, se inserta en alguna permutación de la subsecuencia de tres elementos , o en algunos casos en la subsecuencia de dos elementos . De manera similar, los elementos y del segundo grupo se insertan cada uno en una subsecuencia de longitud como máximo siete, utilizando tres comparaciones. De manera más general, el número de comparaciones en el peor de los casos para los elementos del grupo th es , porque cada uno se inserta en una subsecuencia de longitud como máximo . ^{[1] [2] [3] [4]} Sumando el número de comparaciones utilizadas para todos los elementos y resolviendo la relación de recurrencia resultante , este análisis se puede utilizar para calcular los valores de , dando la fórmula ^[7] ${\displaystyle S}$ ${\displaystyle y_{4}}$ ${\displaystyle (x_{1},x_{2},x_{3})}$ ${\displaystyle y_{3}}$ ${\displaystyle (x_{1},x_{2},y_{4})}$ ${\displaystyle (x_{1},x_{2})}$ ${\displaystyle y_{6}}$ ${\displaystyle y_{5}}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle 2^{i+1}-1}$ ${\displaystyle C(n)}$

${\displaystyle C(n)=\sum _{i=1}^{n}\left\lceil \log _{2}{\frac {3i}{4}}\right\rceil \approx n\log _{2}n-1.415n}$

o, en forma cerrada , ^[8]

${\displaystyle C(n)=n{\biggl \lceil }\log _{2}{\frac {3n}{4}}{\biggr \rceil }-{\biggl \lfloor }{\frac {2^{\lfloor \log _{2}6n\rfloor }}{3}}{\biggr \rfloor }+{\biggl \lfloor }{\frac {\log _{2}6n}{2}}{\biggr \rfloor }.}$

Porque los números de comparaciones son ^[1] ${\displaystyle n=1,2,\dots }$

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... (secuencia A001768 en la OEIS )

Relación con otros tipos de comparación

El algoritmo se denomina ordenamiento por fusión e inserción porque las comparaciones iniciales que realiza antes de su llamada recursiva (emparejando elementos arbitrarios y comparando cada par) son las mismas que las comparaciones iniciales del ordenamiento por fusión , mientras que las comparaciones que realiza después de la llamada recursiva (usando la búsqueda binaria para insertar elementos uno por uno en una lista ordenada) siguen el mismo principio que el ordenamiento por inserción . En este sentido, es un algoritmo híbrido que combina tanto el ordenamiento por fusión como el ordenamiento por inserción. ^[9]

Para entradas pequeñas (hasta ), su número de comparaciones es igual al límite inferior de la ordenación por comparación de . Sin embargo, para entradas más grandes, el número de comparaciones realizadas por el algoritmo de inserción-fusión es mayor que este límite inferior. La ordenación por inserción-fusión también realiza menos comparaciones que los números de ordenación , que cuentan las comparaciones realizadas por la ordenación por inserción binaria o la ordenación por fusión en el peor de los casos. Los números de ordenación fluctúan entre y , con el mismo término principal pero un factor constante peor en el término lineal de orden inferior. ^[1] ${\displaystyle n=11}$ ${\displaystyle \lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n}$ ${\displaystyle n\log _{2}n-0.915n}$ ${\displaystyle n\log _{2}n-n}$

El ordenamiento por fusión-inserción es el algoritmo de ordenamiento con las comparaciones mínimas posibles para elementos siempre que , y tiene la menor cantidad de comparaciones conocidas para . ^{[10] [11]} Durante 20 años, el ordenamiento por fusión-inserción fue el algoritmo de ordenamiento con la menor cantidad de comparaciones conocidas para todas las longitudes de entrada. Sin embargo, en 1979 Glenn Manacher publicó otro algoritmo de ordenamiento que utilizaba incluso menos comparaciones, para entradas lo suficientemente grandes. ^{[3] [5]} Sigue sin saberse exactamente cuántas comparaciones se necesitan para ordenar, para todos los , pero el algoritmo de Manacher y los algoritmos de ordenamiento posteriores que batieron récords han utilizado modificaciones de las ideas de ordenamiento por fusión-inserción. ^[3] ${\displaystyle n}$ ${\displaystyle n\leq 22}$ ${\displaystyle n\leq 46}$ ${\displaystyle n}$

Referencias

1. Ford, Lester R. Jr. ; Johnson, Selmer M. (1959), "Un problema de torneo", American Mathematical Monthly , 66 : 387–389, doi :10.2307/2308750, MR  0103159
2. Williamson, Stanley Gill (2002), "2.31 Inserción de fusión (Ford–Johnson)", Combinatoria para la informática , Libros de matemáticas de Dover, Courier Corporation, págs. 66–68, ISBN 9780486420769
3. Mahmoud, Hosam M. (2011), "12.3.1 El algoritmo Ford–Johnson", Ordenación: una teoría de distribución , Wiley Series in Discrete Mathematics and Optimization, vol. 54, John Wiley & Sons, págs. 286–288, ISBN 9781118031131
4. Knuth, Donald E. (1998), "Inserción de fusión", El arte de la programación informática , vol. 3: Ordenación y búsqueda (2.ª ed.), págs. 184-186
5. Manacher, Glenn K. (julio de 1979), "El algoritmo de ordenamiento Ford-Johnson no es óptimo", Journal of the ACM , 26 (3): 441–456, doi : 10.1145/322139.322145
6. La descripción original de Ford y Johnson (1959) ordenaba los elementos en orden descendente. Los pasos que se enumeran aquí invierten el resultado, siguiendo la descripción de Knuth (1998). El algoritmo resultante realiza las mismas comparaciones, pero produce un orden ascendente.
7. Knuth (1998) atribuye la fórmula de suma a la tesis doctoral de A. Hadian de 1960. La fórmula de aproximación ya había sido propuesta por Ford y Johnson (1959).
8. Guy, Richard K .; Nowakowski, Richard J. (diciembre de 1995), " Problemas mensuales sin resolver, 1969-1995", American Mathematical Monthly , 102 (10): 921–926, doi :10.2307/2975272
9. Knuth (1998), p. 184: "Dado que implica algunos aspectos de fusión y algunos aspectos de inserción, lo llamamos inserción de fusión ".
10. Peczarski, Marcin (2004), "Nuevos resultados en ordenamiento por comparación mínima", Algorithmica , 40 (2): 133–145, doi :10.1007/s00453-004-1100-7, MR  2072769
11. Peczarski, Marcin (2007), "El algoritmo Ford-Johnson sigue imbatible para menos de 47 elementos", Information Processing Letters , 101 (3): 126–128, doi :10.1016/j.ipl.2006.09.001, MR  2287331