comprensión y solución de K-Way se fusionan tipo

Question

Am a

1) contar el número de comparaciones necesarias por K-way merge sort para ordenar permutación aleatoria de números de 0 a N-1.

2)

para contar el número de movimientos de datos necesarios para K-Way ordenamiento por mezcla o permutación de tipo aleatorio de números de 0 a N-1.

Entiendo cómo la combinación de dos vías funciona correctamente y entiendo muy bien el código. Mi problema ahora es que no sé cómo comenzar y necesito un poco de ayuda. ¿Cómo convierto la clasificación de combinación bidireccional en K-Way para que pueda resolver los problemas anteriores?

He buscado en Google por un tiempo pero no encuentro ningún tutorial que me ayude a entender muy bien el "tipo de combinación de k-Way".

Necesito una buena explicación de qué hacer para poder tomarlo desde allí y hacerlo por mi cuenta.

Como dije, entiendo el modo bidireccional, entonces, ¿cómo puedo pasar al tipo de combinación K-Way? ¿Cómo implemento el K-way?

Gracias por ayudarnos.

EDITAR

** He leído algunos post http://bchalk.com/work/view/k_way_merge_sort que montículo binario debe ser utilizado para implementar K-way fusión. ¿Eso es así o hay otras formas?

** ¿Cómo puedo dividir mi lista en K? ¿Hay alguna forma especial de hacerlo?

Answer 1

Cuando k > 2, los elementos principales de cada uno de los flujos de entrada normalmente se mantienen en una estructura de minheap. Esto hace que sea más fácil encontrar el mínimo de los n valores, sacar ese valor del montón e insertar un valor de reemplazo del flujo de entrada correspondiente.

Un montón hace O(lg2 k) comparaciones para cada inserción, por lo que el trabajo total para una combinación k de n elementos es n * lg2(k).

Eventhough se preguntó acerca de C# y Java, se puede aprender cómo hacerlo mirando el código de la biblioteca estándar de Python para una combinación k-way: http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l323

para responder a su otra pregunta, no hay manera especial para dividir tu lista en K grupos. Simplemente tome los primeros elementos N/k en la primera matriz, los siguientes elementos N/k en la siguiente, etc. Ordene cada matriz y luego combínelas usando pilas como se mencionó anteriormente.

Answer 2

Siempre se puede pensar en una combinación de k-way como una serie de combinaciones bidireccionales, es decir, realizar una fusión bidireccional con el resultado de la primera y segunda, y la tercera: Merge(Merge(L1, L2), L3) y así sucesivamente. Aún más rápido sería dividirlo dos veces: Merge(Merge(L1, L2), Merge(L3, L4)). Como puede ver, para un tipo k-way, entonces necesitaría algún tipo de bucle (recursión).