arrays - quick - merge sort recursive java
Con respecto a la fusión en el lugar en una matriz (3)
Hay varios algoritmos para hacer esto, ninguno de los cuales es muy fácil de intuir. La idea clave es usar una parte de los arreglos para fusionarse como un búfer, luego hacer una combinación estándar usando este búfer para el espacio auxiliar. Si luego puedes reposicionar los elementos para que los elementos del búfer estén en el lugar correcto, estás de oro.
He escrito una implementación de uno de estos algoritmos en mi sitio personal si está interesado en verlo. Se basa en el documento "Práctica en el lugar de fusión" por Huang y Langston. Probablemente querrá revisar ese documento para tener una idea.
También he escuchado que hay buenos algoritmos adaptativos para esto, que usan un búfer de tamaño fijo de su elección (que podría ser O (1) si lo desea), pero luego escalan con elegancia con el tamaño del búfer. No sé nada de esto de la cabeza, pero estoy seguro de que una búsqueda rápida de "combinación adaptativa" podría aparecer algo.
Me encontré con la siguiente pregunta.
Dada una matriz de n elementos y un entero k donde k < n . Los elementos { a 0 ... a k } y { a k +1 ... a n } ya están ordenados. Dé un algoritmo para clasificar en tiempo O ( n ) y espacio O (1).
No me parece que se pueda hacer en tiempo O ( n ) y espacio O (1). El problema realmente parece estar preguntando cómo hacer el paso de fusión de mergesort pero in-place. Si fuera posible, ¿no se implementaría la combinación de esa manera? No puedo convencerme a mí mismo y necesito una opinión.
No, no es posible, aunque mi trabajo sería mucho más fácil si fuera :).
Tienes un factor O (log n) que no puedes evitar. Puede elegir tomarlo como tiempo o espacio, pero la única forma de evitarlo es no ordenar. Con el espacio O (log n) puede crear una lista de continuaciones que hacen un seguimiento de dónde escondió los elementos que no encajaban. Con la recursión, esto se puede hacer para caber en el montón O (1), pero eso es solo mediante el uso de marcos de pila O (log n) en su lugar.
Aquí está el progreso de las probabilidades y los emparejamientos de clasificación de mezcla de 1-9. Observe cómo necesita la contabilidad del espacio de registro para rastrear las inversiones de orden causadas por las restricciones gemelas del espacio constante y los swaps lineales.
. - 135792468 . - 135792468 : .- 125793468 : .- 123795468 #.:- 123495768 :.- 123459768 .:- 123456798 .- 123456789 123456789
Hay algunas condiciones de contorno delicadas, un poco más difíciles que la búsqueda binaria para hacer las cosas bien, e incluso en esta forma (posible), y por lo tanto, un problema de tarea mal hecho; Pero un ejercicio mental realmente bueno.
Actualización Aparentemente estoy equivocado y hay un algoritmo que proporciona O (n) tiempo y O (1) espacio. He descargado los documentos para ilustrarme y retirar esta respuesta como incorrecta.
This parece indicar que es posible hacerlo en el espacio O (lg ^ 2 n). No puedo ver cómo probar que es imposible fusionarse en un espacio constante, pero tampoco puedo ver cómo hacerlo.
Edit: Chasing references, Knuth Vol 3 - El ejercicio 5.5.3 dice "Un algoritmo de L. Trabb-Pardo considerablemente más complicado proporciona la mejor respuesta posible a este problema: es posible realizar una fusión estable en tiempo O (n) y estable clasificación en tiempo O (n lg n), utilizando solo O (lg n) bits de memoria auxiliar para un número fijo de variables de índice.
Más references que no he leído. Gracias por un problema interesante.
Edición adicional: este artículo afirma que el artículo de Huang y Langston tiene un algoritmo que combina dos listas de tamaño myn en el tiempo O (m + n), por lo que la respuesta a su pregunta parece ser sí. Lamentablemente no tengo acceso al artículo, por lo que debo confiar en la información de segunda mano. No estoy seguro de cómo conciliar esto con el pronunciamiento de Knuth de que el algoritmo Trabb-Pardo es óptimo. Si mi vida dependiera de ello, iría con Knuth.
Ahora veo que esto se ha preguntado como una question anterior sobre Desbordamiento de pila number veces. No tengo el corazón para marcarlo como un duplicado.
Huang B.-C. y Langston MA, Práctica de fusión en el lugar, Com. ACM 31 (1988) 348-352