Discusión:Ordenamiento por combinación

La ordenación por combinación en el lugar tiene la misma complejidad temporal que la ordenación por combinación fuera de lugar

El artículo menciona un tiempo de ejecución de para la ordenación por fusión en el lugar, lo cual es incorrecto. Debería ser . — Comentario anterior sin firmar agregado por Dhruvbird ( discusión • contribs ) 04:40, 16 de marzo de 2015 (UTC) [ responder ] ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n\log n)}$

Mergesort no requiere espacio 2n

Dos matrices ordenadas pueden fusionarse en el mismo lugar en tiempo O(n), usando espacio O(1) (variable temporal para intercambiar dos elementos). Para implementar la ordenación por fusión, esta fusión debe repetirse log(n) veces. Puedes implementar fácilmente la ordenación por fusión de abajo a arriba de manera estable y en el mismo lugar. Comienza con n=1 y fusiona las porciones de i*n a i*(n+1) para i=0 hasta que agotes la matriz. Para n=1 esto ordena pares de elementos. Luego multiplica n por 2 y reinicia hasta que n >= tamaño de la matriz. — Comentario anterior sin signo agregado por 87.198.115.102 (discusión) 07:53, 26 de junio de 2013 (UTC) [ responder ]

Es mucho más difícil de lo que imaginas, mira [1] por ejemplo. El problema es que empiezas a tener posiblemente una cantidad de cadenas para fusionar en lugar de solo dos o tres después de mover algunos elementos. No creo que uno pueda llamarlo con razón un mergesort después de eso, sino más bien un tipo calificado de mergesort con un algoritmo complicado. Por cierto, las nuevas discusiones deberían colocarse al final, solo haz clic en "nueva sección" para iniciar una. Dmcq ( discusión ) 08:54, 26 de junio de 2013 (UTC) [ responder ]

Yo apoyaría la observación del primer autor. No es más que una tarde de codificación para obtener la solución. Piense en cómo funciona para una lista enlazada y obtendrá una inferencia para datos estáticos, tal como observó el primer autor. Las ordenaciones por combinación no están en una categoría de algoritmos considerados difíciles de implementar, incluso cuando son híbridos. — Comentario anterior sin firmar agregado por 80.254.148.163 ( discusión ) 17:44, 13 de junio de 2014 (UTC) [ responder ]

Combinación de fusiones naturales

Leí por primera vez sobre este tipo de ordenación por fusión en Scheme and the Art of Programming, de George Springer y Daniel P. Friedman.
Lo llaman ordenación por fusión natural.

Aquí hay un primer intento (en Python) de ordenar por combinación de abajo hacia arriba y en el lugar:

def count_sorted( elementos, inicio=0 ): para x en rango(inicio+1,len(elementos)): si elementos[x-1]>elementos[x]: retorna x - inicio; retorna len(items) - inicio;def reinsert( elementos, val, inicio, fin ): para x en rango(inicio, fin-1): si elementos[x+1] > val : elementos[x] = val devolver demás: elementos[x] = elementos[x+1] elementos[fin-1] = valdef merge_sublists( elementos, izquierda, derecha ): para x en el rango (0, izquierda): si elementos[x] > elementos[izquierda]: val = elementos[x] elementos[x] = elementos[izquierda] reinsertar( elementos, val, izquierda, izquierda+derecha )def merge( elementos ): izquierda= count_sorted(elementos) mientras izquierda < len(elementos): derecha = count_sorted( elementos, izquierda ) merge_sublists( elementos, izquierda, derecha ) izquierda = izquierda + derecha

Una posible optimización es que cuando la sublista ordenada más larga es uno, encontrar la lista ordenada inversa más larga e invertirla.

-David Medlock, 13 de enero de 2006

¿Es ese Timsort ? -- Damian Yerrick ( discusión | acecho ) 17:45 19 dic 2011 (UTC) [ responder ]

Esto es Theta(n^2) con fusiones Theta(n) y complejidad Theta(n) en reinserción. 188.120.84.157 (discusión) 04:42 26 abr 2014 (UTC) [ responder ]

La fuente del algoritmo en cuestión

Se afirma que el algoritmo fue inventado por von Neumann en 1945. Sin embargo, la referencia es al libro de Knuth de 1998 (¡no a la primera edición, por cierto!). La referencia a un trabajo original realizado por von Neumann y publicado en 1945 es necesaria. Si el algoritmo presentado se describe solo en el libro de Knuth de 1998, es de 1998, no de 1945. Riemann'sZeta ( discusión ) 20:11 12 abr 2011 (UTC) [ responder ]

No se requiere una referencia primaria. Knuth es WP:RS y la declaración debería ser WP:V . Si afirmas que Knuth no dice que von Neumann inventó el algoritmo en 1945, entonces eso sería un ataque WP:V . No parece que esa sea tu disputa; en cambio, simplemente quieres un documento con una fecha de 1945. Ese no es un requisito de WP para una cita. Glrx ( discusión ) 20:30, 12 de abril de 2011 (UTC) [ responder ]

Se ha sugerido que Von Neumann obtuvo la idea de la ordenación por fusión de las alzadoras de tarjetas perforadas que datan de 1937. La operación principal de una alzadora es fusionar dos barajas ordenadas de tarjetas perforadas, esencialmente una pasada de una ordenación por fusión de abajo hacia arriba. alzadoras. Rcgldr ( discusión ) 16:18 3 feb 2020 (UTC) [ responder ]

Agregar ejemplos de pseudocódigo no recursivo

Como algoritmo que se puede ejecutar de forma recursiva y no recursiva, me parece que añadir un ejemplo de un algoritmo de ordenamiento por fusión no recursivo podría hacer que este artículo fuera más completo. Yo mismo no soy especialmente apto para escribir pseudocódigo claro y comprensible, pero creo que un ejemplo aquí sería una buena idea. OceanicMeerkat ( discusión ) 05:52 27 ene 2014 (UTC) [ responder ]

El pseudocódigo ascendente de ejemplo que se encuentra cerca de la parte superior del artículo no es recursivo. Rcgldr ( discusión ) 08:19 21 feb 2014 (UTC) [ responder ]

La ordenación por fusión no recursiva es considerablemente más rápida que la ordenación por fusión recursiva (un 40 % más rápida). Sin embargo, se deriva de la eliminación de la recursión de cola y es bastante complicada. El sistema I# para Java tiene una implementación de la ordenación por fusión no recursiva en el lenguaje Java. El sistema I# para C# tiene la ordenación por fusión no recursiva en C#. — Comentario anterior sin firmar añadido por 1.129.96.33 ( discusión ) 08:01, 8 julio 2016 (UTC)[ responder ]

La implementación de arriba hacia abajo es simplemente errónea

Intente escribir eso para la computadora real. Uno de los errores obvios es que divide [0, mid], [mid + 1, high] pero luego fusiona [0, mid - 1], [mid, high] — Comentario anterior sin firmar agregado por 86.57.194.198 (discusión) 06:28, 18 de marzo de 2014 (UTC) [ responder ]

¿Lo arreglé? Glrx ( discusión ) 21:43 26 mar 2014 (UTC) [ responder ]

Suponiendo que hayas añadido el comentario sobre que iEnd es el final de la matriz y no parte de ella, el problema está solucionado. El ejemplo comenzó como código de trabajo real y la mayoría de los cambios simplemente eliminaron las declaraciones de tipo de variable. La división es [0, mid] y [mid, high], y el segundo índice de cada par es el "final" de la submatriz y no parte de ella, por lo que los índices de división reales serían [0, mid-1], [mid, high-1]. Rcgldr ( discusión ) 18:58, 29 de abril de 2014 (UTC) [ responder ]

Mis ediciones. Glrx ( discusión ) 23:43 29 abr 2014 (UTC) [ responder ]

La mitad izquierda y la mitad derecha se fusionan de arriba hacia abajo

Conceptualmente, si divides algo en dos mitades alrededor de un punto medio (entero truncado), entonces la primera mitad será "inicio" a "punto medio", la segunda mitad será "punto medio + 1" a "fin". Por ejemplo, inicio = 0, fin = 1, punto medio es 0, "mitad izquierda" es 0, "mitad derecha" es 1. Con el código actual, "mitad izquierda" sería 0, "mitad derecha" sería 0 y 1, es decir, la lista completa.
En Cracking the Coding Interview, p.118, que utiliza un código muy similar al ejemplo de WP, la primera mitad es "inicio a punto medio", la segunda mitad es "punto medio + 1 a fin", como esperaba.
Cambié la mitad derecha a punto medio + 1, pero mi cambio fue revertido por User:Glrx con el comentario "índices inclusivos/exclusivos". Más adelante en el código WP hay un comentario: "// la mitad izquierda es A[iBegin :iMiddle-1] // la mitad derecha es A[iMiddle:iEnd-1 ]". Pero no creo que eso funcione con números enteros truncados; en mi ejemplo de una lista de dos elementos, la mitad izquierda sería de 0 a -1, es decir, te has salido de la matriz. Funcionaría con números enteros que se redondean hacia arriba, pero ese no es el caso con los lenguajes de estilo C, que parece ser el estilo en el que está escrito el código.
Además, incluso si estuviéramos redondeando hacia arriba, el comentario implica que el punto medio está solo en la mitad derecha, mientras que con el código tal como está escrito, en realidad está en ambas mitades. ¿Alguien puede aclararme qué está pasando aquí? -- Merlinme ( discusión ) 20:32, 8 de diciembre de 2014 (UTC) [ responder ]

Mmm. Vale, lo entiendo. Si pasas un "fin" de 2 para el ejemplo de lista de tamaño dos, entonces el medio es 1 y funciona. No estoy seguro de que sea la forma más intuitiva de hacer las cosas (¿por qué hacerlo de forma diferente al enfoque de búsqueda binaria comúnmente entendido?), pero funciona. -- Merlinme ( discusión ) 20:48, 8 de diciembre de 2014 (UTC) [ responder ]

Acabo de echar un vistazo a "Introducción a los algoritmos" (CLRS). En mi edición, MERGE-SORT está en la página 34 y utiliza q = ((p+r) / 2), seguido de MERGE-SORT(A, p, q), MERGE-SORT(A, q + 1, r). Ya he mencionado Cracking the Coding Interview, página 118. Véase también: [2], que hace referencia a "Algoritmos en Java, partes 1-4, 3.ª edición de Robert Sedgewick. Addison Wesley, 2003" y "Programming Pearls de Jon Bentley. Addison Wesley, 1986". Esa página web utiliza "m = n / 2, sort a[1..m], sort a[m+1..n]".

Si existe un modismo estándar en los libros de referencia para un algoritmo en particular, entonces no estoy realmente convencido de que Wikipedia deba usar un modismo alternativo. En el mejor de los casos, es confuso. Incluso se podría argumentar que se trata de una investigación original (¿a qué lo citarías?), aunque no estoy seguro de llegar tan lejos. -- Merlinme ( discusión ) 21:03 8 dic 2014 (UTC) [ responder ]

Los "índices inclusivos/exclusivos" parecen ser la norma para la mayoría de los lenguajes donde el primer índice de una matriz es 0. Por ejemplo, las llamadas a C++ STL (Standard Template Library) para std::sort o std::stable_sort son primer iterador, iterador final. Los parámetros qsort() de C/C++ son puntero a la matriz, ..., tamaño de la matriz. El código típico que recorre una matriz usa algo como for ( i=0; i<size; i+=1). El algoritmo STL de HP/Microsoft stable_sort, que es una ordenación por fusión casi de abajo hacia arriba, divide la matriz/vector en dos partes usando (A, start, mid), (A, mid, end). La división se realiza de modo que la matriz temporal solo necesite tener la mitad del tamaño de la matriz original, de lo contrario, es una ordenación por fusión de abajo hacia arriba. Rcgldr ( discusión ) 00:56, 23 de noviembre de 2015 (UTC) [ responder ]

Implementación de abajo hacia arriba utilizando listas

Esta es una nueva sección del artículo. Es el método principal que se utiliza para ordenar listas enlazadas, por lo que debería incluirse en el artículo. Las implementaciones de la función std::list::sort() de la biblioteca de plantillas estándar de C++ STL utilizan este algoritmo. Rcgldr ( discusión ) 00:37, 23 de noviembre de 2015 (UTC) [ responder ]

Mi objeción no es a la inclusión de este algoritmo, sino a la presentación. Aproximadamente la mitad del pseudocódigo se dedica a implementar una optimización, en lugar del algoritmo básico. Q VVERTYVS ( ¿hm? ) 11:06, 29 de noviembre de 2015 (UTC) [ responder ]

No debería haber revertido el tema directamente. Me disculpo por ello. Q VVERTYVS ( ¿hm? ) 11:18, 29 de noviembre de 2015 (UTC) [ responder ]

El artículo está bien ahora. No era necesario incluir un segundo ejemplo demasiado detallado de merge(), así que lo quité y dejé la parte clave del algoritmo, que es en lo que debería centrarse la sección. Rcgldr ( discusión ) 11:42 29 nov 2015 (UTC) [ responder ]

Estoy de acuerdo en que la versión optimizada era inapropiada.

Me opongo a la manipulación de código: edición cuyo propósito es cambiar el estilo y los nombres existentes al estilo preferido de otro editor.

Glrx ( discusión ) 05:09 1 dic 2015 (UTC) [ responder ]

¿Se refiere esto a cambiar los ceros a cero? Si es así, no estoy seguro de cuál sería más claro para el público objetivo. Rcgldr ( discusión ) 22:32 3 dic 2015 (UTC) [ responder ]

No. Glrx ( discusión ) 05:23 5 dic 2015 (UTC) [ responder ]

¿Entonces, qué parte de esta sección fue objeto de un código modificado? Es una sección nueva y sigue el estilo de la sección de ordenación por fusión de arriba hacia abajo para listas. Rcgldr ( discusión ) 23:55, 5 de diciembre de 2015 (UTC) [ responder ]

Esta sección debe renombrarse claramente como implementación de C++ o eliminarse. Utiliza "node.next", que de otra manera no tendría sentido. Nombrar una lista enlazada de C++ como "nodo" no convierte el código de C++ en un pseudocódigo o en un ejemplo de uso general. 109.194.226.45 (discusión) 13:31 14 mar 2019 (UTC) [ responder ]

Ejemplo de animación

¿Alguien más piensa que el ejemplo de animación tiene comparaciones extrañas una vez que uno de los lados (el lado izquierdo en todos los casos) se queda sin celdas? Pensé que el objetivo de todo el algoritmo era aprovechar el hecho de que las particiones que se fusionan están ordenadas. — Comentario anterior sin firmar agregado por 88.192.22.239 (discusión) 14:56, 14 de abril de 2016 (UTC) [ responder ]

Además, la animación parece estar mal. No sigue el código de ejemplo de arriba hacia abajo porque sigue volviendo a otras matrices paralelas y trabajando en ellas EN LUGAR DE ordenar por completo la submatriz izquierda Y SOLO LUEGO volver y ordenar la submatriz derecha. — Comentario anterior sin firmar agregado por 73.157.112.58 (discusión) 02:14, 18 de diciembre de 2021 (UTC) [ responder ]

¿Podríamos tener una descripción en inglés?

El artículo es completamente oscuro para aquellos de nosotros que no podemos leer códigos informáticos. Se divide la lista en sublistas y luego se fusionan, pero ¿cómo funciona eso? ¿Cómo se fusionan dos listas ordenadas en una? El artículo simplemente asume que es fácil, en lo que respecta al texto. El diagrama también muestra listas que simplemente se fusionan y emergen como ordenadas, sin explicación del proceso de fusión. Cyclopaedic ( discusión ) 09:07, 2 de agosto de 2016 (UTC) [ responder ]

Apoyo firmemente esa idea. Lo *único* que se supone que este artículo debe hacer no lo hace: explicar la fusión, como en el ordenamiento por fusión. Casi todo lo demás en este extenso artículo no es tan especial como para el ordenamiento por fusión. El paso de fusión sí lo es. — Comentario anterior sin firmar añadido por 2003:F3:EF19:EB00:5D7F:F4D5:2433:6888 (discusión) 08:51 9 abr 2023 (UTC)[ responder ]

Expresión para el punto medio

He vuelto a utilizar la fórmula del punto medio de forma más clara (a+b)/2. La a+(b-a)/2forma no resulta obvia para la mayoría de las personas.

WP debería describir algoritmos. En una implementación de pseudocódigo, no se especifican los anchos de los números porque las operaciones son abstractas. Se supone que los cálculos no se desbordan.

Además, la URL https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html es un blog. No es una fuente confiable.

En Binary search algorithm#Implementation issues , se hace un gran comentario sobre el error de la biblioteca Java, pero esa afirmación es engañosa. Hay una razón por la que el error no se descubrió durante años: solo ocurriría si alguien hiciera algo poco práctico. Solo sería un problema grave cuando se utilizan índices de 32 bits en un espacio de direcciones de 64 bits. Pero los índices en espacios de direcciones de 64 bits deberían ser números de 64 bits. En un espacio de direcciones de 64 bits, podría querer crear una matriz de más de 2 registros ^{de 32 bits} ; debería poder usar la búsqueda binaria en esa matriz. Si el sistema solo permite índices de 32 bits, entonces tengo problemas mayores.

Ahora la carne.

Los números utilizados en el algoritmo son índices en lugar de punteros de bytes. En casos racionales, el tamaño de un registro será de al menos 4 bytes. Por lo tanto, en el caso del espacio de direcciones de 32 bits, los índices de registro serán números de 30 bits. El desbordamiento no será un problema. Lo mismo ocurre con el espacio de direcciones de 64 bits.

El error de Java generó un caso irracional: creó una matriz de 1100 millones de bytes individuales e intentó buscar en ella; los números se desbordaron y generaron una referencia fuera de límites de la matriz. Piense en esa matriz de bytes por un minuto. ¿Una búsqueda binaria de una matriz con 1100 millones de elementos que solo puede tener 256 elementos distintos?

WP no debería enfatizar esos casos didácticos. Glrx ( discusión ) 20:02 10 oct 2017 (UTC) [ responder ]

Variantes

Esta sección incluye las afirmaciones: "... producir un algoritmo de fusión en el lugar que se puede combinar con una ordenación por fusión estándar (de arriba hacia abajo o de abajo hacia arriba) ..." "la noción de "en el lugar" se puede relajar para significar "tomar espacio de pila logarítmico", porque la ordenación por fusión estándar requiere esa cantidad de espacio para su propio uso de pila", pero el espacio de pila logarítmico solo se usa en la ordenación por fusión de arriba hacia abajo, no en la de abajo hacia arriba. Rcgldr ( discusión ) 16:43, 9 de diciembre de 2017 (UTC) [ responder ]

@ Rcgldr : ¿Puede ser que una rutina de fusión estable en el lugar requiera un tamaño de pila logarítmico? Entonces, si la combinamos con un algoritmo ascendente de tamaño de pila constante, produciríamos una combinación de ordenamiento por fusión estable de tamaño de pila logarítmico, ¿no es así? -- CiaPan ( discusión ) 17:49, 9 de diciembre de 2017 (UTC) [ responder ]

@ CiaPan : Mi punto es que el artículo dice que "la ordenación por combinación estándar requiere esa cantidad de espacio", no que la ordenación por combinación estándar esté modificada para que esté en su lugar. Rcgldr ( discusión ) 00:06, 21 de diciembre de 2017 (UTC) [ responder ]

Problema con el ejemplo de arriba hacia abajo: ¿el resultado está en un lado arbitrario?

Espero no estar pasando por alto nada aquí, pero después de revisarlo muchas veces creo que falta algo en el ejemplo de arriba hacia abajo a partir de la edición del 24 de mayo de 2018.

Si realiza la ordenación con una matriz de tamaño 16, entonces la matriz ordenada resultante termina en la matriz original (la que era "A" en TopDownMergeSort en la parte superior).

...pero si realiza la ordenación con una matriz de tamaño 8, entonces la matriz ordenada resultante termina en la matriz de trabajo (la que era "B" en TopDownMergeSort en la parte superior).

No hay ninguna pieza al final que determine si el resultado está en la matriz incorrecta y lo copie si ese es el caso.

Jlkeegan ( discusión ) 03:57 15 jun 2018 (UTC) [ responder ]

No entiendo lo que quieres decir. Es posible que no te des cuenta de que las matrices reales a las que hacen referencia los símbolos Ay Bel intercambio en cada nivel de recursión, como TopDownSplitMerge(B[], iBegin, iEnd, A[])se invoca a sí mismo con

 TopDownSplitMerge(A, iBegin, iMiddle, B); // ordena la carrera izquierda TopDownSplitMerge(A, iMiddle, iEnd, B); // ordena la ejecución correcta

Como resultado, Asignifica una matriz de origen para la división y una matriz de destino para la fusión en el nivel actual de recursión que puede ser la misma que la matriz de destino de todo el procesamiento o la copia de trabajo (temporal) de los datos de origen realizada al principio. Y de manera similar (pero opuesta) para B, que es una matriz de origen temporal para la fusión en el nivel actual de recursión . Que sea de esta manera o de esa depende de si es un nivel de recursión par o impar. -- CiaPan ( discusión ) 08:51, 15 de junio de 2018 (UTC) [ responder ]

Ping añadido: @Jlkeegan: -- CiaPan ( discusión ) 10:52 15 jun 2018 (UTC) [ responder ]

No, ya lo vi. Es difícil ver el problema si solo estás leyendo el código. Si lo analizas como un ejemplo real y llevas un registro de qué matriz real se modifica en qué punto y prestas atención a cuántos niveles de profundidad alcanzas en entradas de diferentes tamaños, puedes ver el problema.

TopDownMerge (el único método que realiza cambios) decide en qué matriz escribir en función de la matriz que se pasó como cuarto argumento. Ese argumento lo proporciona el primer argumento de la llamada TopDownSplitMerge anterior, que fue proporcionada por el cuarto argumento de la llamada TopDownSplitMerge anterior. La cantidad de TopDownSplitMerge en la pila determina cuántas veces se cambió de una matriz a otra.

Hazlo en papel y lleva un registro de en qué matriz se escriben las cosas REALES. Si tienes una matriz de tamaño 16, el resultado residirá en la matriz "A" inicial proporcionada a TopDownMergeSort al principio. Pero si tienes una matriz de tamaño 8, el resultado terminará en la matriz "B" inicial proporcionada a TopDownMergeSort al principio. (El hecho de que los nombres de los parámetros sean todos A y B es confuso: ignora eso y lleva un registro, o haz todo esto con una baraja de cartas).

Debe haber algún paso al final para verificar si la profundidad era par o impar y luego, en uno de esos casos, copiar la matriz ordenada resultante de B a A (si la fusión final hubiera sido de A a B). (De nuevo, a menos que me equivoque, pero estoy 99% seguro de que no lo estoy). Jlkeegan ( discusión ) 17:38 15 jun 2018 (UTC) [ responder ]

@Jlkeegan: NO lo hagas en papel, sino compila el código y ejecútalo en una computadora. Después de todo, ahí es donde se supone que debe ejecutarse el código. Pero, si insistes en la ejecución manual, prueba primero con matrices más cortas, de 2 y 3 elementos para empezar. Y recuerda completarlo : no lo rompas en el nivel más profundo de recursión, sino que continúa hasta volver al punto de partida.

De todos modos, lo que sea que hayas hecho en tu artículo, no cambia el código, ¿verdad? Y el código muestra claramente que (después de completar todas las llamadas recursivas) la instancia superior de TopDownSplitMergepasa su A[]argumento como último parámetro a TopDownMerge. Como resultado, la última fusión coloca los datos fusionados en la matriz de destino original. Lo cual es correcto. No importa cuán larga sea la matriz (si contiene dos, tres, ocho, dieciséis o un millón de elementos) y cuántos niveles de recursión estén involucrados, la fusión final siempre coloca los datos en la matriz correcta. -- CiaPan ( discusión ) 10:43, 18 de junio de 2018 (UTC) [ responder ]

animación

@ CiaPan : Copiado de mi página de discusión:

Hola, has eliminado el archivo:Merge sort animation2.gif aquí: Special:Diff/887750333.
¿Por qué crees que no es una representación de mergesort? --CiaPan (discusión) 3:10 am, Hoy (UTC−4)

(Lo eliminé en otro lugar; no estoy seguro de por qué no di una explicación tan detallada aquí). Mi problema es que no muestra la fusión real de las sublistas, que en cambio parece ocurrir instantáneamente. En contraste, la animación en el cuadro de información sí muestra la fusión. – Deacon Vorbis  ( carbon  •  videos ) 12:22, 15 de marzo de 2019 (UTC) [ responder ]

@ Deacon Vorbis : Por supuesto, la imagen no muestra cada detalle de la transformación de datos, solo muestra una imagen de la matriz completa al final de cada etapa de procesamiento (aquí, una etapa de procesamiento es la rutina de fusión). De manera similar, File:Bubble sort animation.gif o File:Insertion sort animation.gif muestran un estado de la matriz después de que cada elemento llega a su lugar de destino en la parte ordenada, pero no después de cada intercambio. Además, la fusión requiere una matriz externa, por lo que el mismo método de presentación simplemente no puede mostrar todo el proceso. De todos modos, sigue siendo una presentación de mergesort. -- CiaPan ( discusión ) 13:01, 15 de marzo de 2019 (UTC) [ responder ]

Bueno, yo podría argumentar que esos tampoco son ideales. Un poco fuera de tema, pero esos tienen mejores alternativas disponibles: c:File:Sorting bubblesort anim.gif y c:File:Insertion sort.gif. Me doy cuenta de que se tendría que hacer un cambio en la presentación debido al uso de una matriz externa, pero ciertamente se podría hacer. Ehh, pero hasta que alguien (posiblemente yo, pero seamos realistas) realmente lo haga, si realmente crees que es mejor incluirlo, entonces siéntete libre de volver a ponerlo; no seguiré objetando. – Deacon Vorbis  ( carbon  •  videos ) 13:27, 15 de marzo de 2019 (UTC) [ responder ]

La animación eliminada muestra la ordenación por fusión de una matriz de números enteros aleatorios. El título anterior a que la cambiara no indicaba en absoluto qué se estaba ordenando. La animación eliminada es en realidad más realista que la otra de este artículo. En una ordenación por fusión real, la matriz que se va a ordenar se dividiría en submatrices más pequeñas y cada submatriz se ordenaría con ordenación por inserción. Luego, las submatrices se fusionarían. Esto es exactamente lo que muestra la animación.

No hay ninguna buena razón para eliminar esta animación. Solo necesitaba un título más descriptivo. Ha estado en este artículo desde al menos 2013. Jrheller1 ( discusión ) 23:49 19 mar 2019 (UTC) [ responder ]

@ Jrheller1 y Deacon Vorbis : No es exactamente el mismo archivo GIF, pero la misma animación ha estado allí durante más de 12 años, desde fines de noviembre de 2006; consulte Special:Diff/90680635#Analysis . :) CiaPan ( discusión ) 07:40, 20 de marzo de 2019 (UTC) [ responder ]

La animación actual (no la eliminada) debe actualizarse

La imagen animada que todavía se ve actualmente entra en conflicto con los algoritmos presentados en el artículo. Lo que muestra la animación es una ordenación por fusión implementada utilizando una cola en lugar de una pila (recursión). Una implementación basada en cola da como resultado una división repetida en amplitud de la matriz hasta que el tamaño de las ejecuciones se reduce a 1 elemento por ejecución. El enfoque de cola no se realiza normalmente porque la complejidad del espacio de la cola es O(n), y el enfoque de cola no se menciona en ninguna parte del artículo. Un enfoque de pila es profundidad primero, izquierda primero: la matriz dividida en dos, la mitad izquierda dividida en dos, el cuarto izquierdo dividido en dos, ..., luego y solo cuando se producen las dos ejecuciones más a la izquierda de tamaño 1, comienza el proceso de fusión, siguiendo la cadena de pila hacia arriba y comenzando en un orden de profundidad primero, izquierda primero. Una solución más simple sería mostrar un enfoque de abajo hacia arriba. En un paso, la matriz inicial se separa en n ejecuciones de tamaño 1 (en realidad, esto no es un paso, ya que la matriz se trata simplemente como n ejecuciones de tamaño 1 sin ninguna manipulación real de los datos), luego, normalmente, las ejecuciones pares e impares se fusionan en orden de amplitud. Esto solo requeriría eliminar los pasos de división intermedios que se muestran en la animación. Rcgldr ( discusión ) 21:42, 21 de marzo de 2019 (UTC) [ responder ]

@Rcgldr : Me temo que estás equivocado. Por favor, comprueba que he entendido bien tu descripción .

La implementación recursiva (pila) hace que los subconjuntos se ordenen en el siguiente orden:

 [0 1] [0 1][2 3] [0 1 2 3] [0 1 2 3] [4 5] [0 1 2 3] [4 5] [6 7] [0 1 2 3] [4 5 6 7] [01234567] [0 1 2 3 4 5 6 7] [8 9] [0 1 2 3 4 5 6 7] [8 9] [10 11] [0 1 2 3 4 5 6 7] [8 9 10 11] [0 1 2 3 4 5 6 7][8 9 10 11][12 13] [0 1 2 3 4 5 6 7][8 9 10 11][12 13][14 15] [0 1 2 3 4 5 6 7][8 9 10 11][12 13 14 15] [0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15] [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]

1. ¿Es eso correcto?
2. ¿Está de acuerdo con la animación?

Por otra parte, la implementación iterativa (cola) ordenaría los subconjuntos de esta manera:

 [0 1][2 3][4 5][6 7][8 9][10 11][12 13][14 15] [0 1 2 3][4 5 6 7][8 9 10 11][12 13 14 15] [0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15] [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]

1. ¿Es eso correcto?
2. ¿Está de acuerdo con la animación?

CiaPan ( discusión ) 22:31 21 mar 2019 (UTC) [ responder ]

Las operaciones de combinación recursivas de pila o de arriba hacia abajo se realizan en este orden (primero en profundidad, primero a la izquierda), utilizando {} para indicar que están combinadas.

 [01234567] [0 1 2 3] [0 1] [0][1] {0 1} [2 3] [2][3] {2 3} {0123} [4 5 6 7] [4 5] [4][5] {4 5} [6 7] [6][7] {6 7} {4 5 6 7} {01234567}

El orden de abajo hacia arriba sería:

 [01234567] [0][1][2][3][4][5][6][7] {0 1} {2 3} {4 5} {6 7} {0123} {4 5 6 7} {01234567}

La animación muestra un ordenamiento de cola, con algunas de las operaciones mostradas en paralelo:

 [01234567] [0 1 2 3] [4 5 6 7] [0 1] [2 3] [4 5] [6 7] [0] [1] [2] [3] [4] [5] [6] [7] {0 1} {2 3} {4 5} {6 7} {0123} {4 5 6 7} {01234567}

Rcgldr ( discusión ) 23:54 21 mar 2019 (UTC) [ responder ]

(ec) @ Rcgldr : Claro, pero sumergirse en sublistas cada vez más pequeñas no cambia el orden de los datos, por lo que es invisible en la animación. Lo que podemos ver son los resultados de la fusión de sublistas, es decir, instantáneas de los retornos de las llamadas recursivas. Por lo tanto, una vez más, observe los cambios en el orden de los datos que se presentan en la animación. ¿Es un algoritmo de profundidad o de amplitud? -- CiaPan ( discusión ) 23:55, 21 de marzo de 2019 (UTC) [ responder ]

@ CiaPan : La animación muestra una matriz de tamaño 8 dividida en 2 submatrices de tamaño 4, que luego se dividen en 4 submatrices de tamaño 2, que luego se dividen en 8 submatrices de tamaño 1. Estas divisiones se realizan en paralelo, seguidas de fusiones en amplitud. Esto se corresponde más estrechamente con una ordenación por fusión basada en cola, excepto que las divisiones basadas en cola se realizan en serie (FIFO), no en paralelo, y la ordenación por fusión basada en cola no se analiza en ninguna parte del artículo. Para una ordenación por fusión de abajo hacia arriba, no hay una división repetida de una matriz, en su lugar, una matriz de tamaño n se trata inmediatamente como n ejecuciones de tamaño 1 (no hay pasos de división reales). Si la animación va a mostrar una ordenación por fusión de abajo hacia arriba, la animación debería mostrar la matriz de 8 dividida en 8 submatrices de tamaño 1 en un solo paso. Rcgldr ( discusión ) 01:44, 22 de marzo de 2019 (UTC) [ responder ]

Rcgldr está comentando la animación que todavía se ve en el artículo. La animación eliminada muestra una ordenación por combinación en mosaico. Consulta la sección "Optimización de la ordenación por combinación". Parece que las submatrices de tamaño 16 aproximadamente se ordenan con la ordenación por inserción y luego se fusionan las submatrices ordenadas. Tal vez la animación eliminada debería moverse a esta sección con un título que indique que es una ordenación por combinación en mosaico. Jrheller1 ( discusión ) 01:55, 22 de marzo de 2019 (UTC) [ responder ]

@ Jrheller1 : - Separé esto en una nueva sección, ya que se trata de una animación diferente. Rcgldr ( discusión ) 03:02, 22 de marzo de 2019 (UTC) [ responder ]

Implementación de abajo hacia arriba: intercambio de referencias a A y B

Tenga en cuenta que C, C++, C#, Java, Python, todos manejan los nombres de matriz como referencias y pueden implementar swap(A,B) que simplemente intercambia las referencias, así que ¿por qué no cambiar el artículo para usar swap(A,B) y poner un comentario sobre el uso de la copia para lenguajes de programación que no admitan un intercambio? Rcgldr ( discusión ) 18:22, 10 de junio de 2019 (UTC) [ responder ]

@ Rcgldr : En C y sus descendientes Ano Bson 'referencias' a objetos sino más bien nombres de variables. No puedes simplemente intercambiar el significado de los dos para hacer que hagan referencia a datos opuestos. Tendrías que reemplazar matrices puras con punteros a matrices y eso abrumaría todo el código con muchos operadores de desreferencia innecesarios (asteriscos de prefijo). Como resultado, en mi humilde opinión, el código sería menos legible, mientras que la legibilidad debería ser uno de los principales objetivos de presentar el código en una enciclopedia . Deja las optimizaciones menores para los manuales de programación. -- CiaPan ( discusión ) 06:10, 11 de junio de 2019 (UTC) [ responder ]

@ CiaPan : El ejemplo de arriba hacia abajo ya tiene una optimización menor, copia A[]a B[], luego invierte los parámetros en las llamadas recursivas para que la dirección de la fusión cambie con el nivel de recursión. Rcgldr ( discusión ) 09:51, 15 de junio de 2019 (UTC) [ responder ]

@ Rcgldr : Además, tendrías que contar los bucles y hacer otro intercambio condicional al final de la rutina para asegurarte de que los datos ordenados finalmente lleguen a la matriz correcta. O devolver esa matriz como un resultado explícito de la rutina. -- CiaPan ( discusión ) 06:12, 11 de junio de 2019 (UTC) [ responder ]

@ CiaPan : Me refería a cuando A[]y B[]se pasan como parámetros a una función. En C o C++, las matrices que se pasan como parámetros se tratan como punteros, myfun(int A[], int B[], ...) es lo mismo que myfun(int *A, int *B, ...). El uso de sizeof(A) dentro de myfun devuelve el tamaño de un puntero, no el tamaño de la matriz, por lo que para C o C++, se necesitaría un tercer parámetro para la cantidad de elementos. La ordenación por fusión de abajo hacia arriba podría usar un contador para la cantidad de pasadas y hacer una copia si la cantidad de pasadas es impar, o similar al ejemplo de arriba hacia abajo, que siempre copia al principio, de abajo hacia arriba siempre podría copiar al final. Rcgldr ( discusión ) 13:40, 11 de junio de 2019 (UTC) [ responder ]

Quizás haya estado un pocotambién WP:NEGRITA

Er... Acabo de echar un vistazo a esta página de discusión y noté la extensa discusión de múltiples versiones del código de ejemplo, después de que lo reescribí.

Como dice el mensaje de confirmación , la motivación para la reescritura fue TopDownSplitMerge():

// Ordena la ejecución dada de la matriz A[] usando la matriz B[] como fuente. // iBegin es inclusivo; iEnd es exclusivo (A[iEnd] no está en el conjunto). void TopDownSplitMerge ( B [], iBegin , iEnd , A []) { if ( iEnd - iBegin < 2 ) // si el tamaño de la ejecución == 1 return ; // considéralo ordenado // divide la ejecución más larga de 1 elemento en mitades iMiddle = ( iEnd + iBegin ) / 2 ; // iMiddle = punto medio // ordena recursivamente ambas ejecuciones de la matriz A[] en B[] TopDownSplitMerge ( A , iBegin , iMiddle , B ); // ordena la ejecución izquierda TopDownSplitMerge ( A , iMiddle , iEnd , B ); // ordenar la ejecución correcta // fusionar las ejecuciones resultantes de la matriz B[] en A[] TopDownMerge ( B , iBegin , iMiddle , iEnd , A ); }                                      

Esto espera que las llamadas recursivas a TopDownSplitMergetomen su entrada de A[]y dejen sus resultados en B[], de modo que la llamada a TopDownMerge()pueda copiarlos nuevamente en A[]. Esto implementa una ordenación en el lugar. Pero, ¿no acabamos de decir que debe TopDownSplitMergeser una ordenación fuera de lugar?

Tras una reflexión más profunda, puede ser que el comentario sea muy engañoso y que el código funcione de una manera increíblemente confusa porque y son duplicados entre sí, por lo que recurramos hasta el final y encontramos los datos de origen en o A[]según B[]el número de niveles de recursión y luego las cosas funcionan al volver hacia arriba. Pero si lo he mirado durante media hora y todavía no puedo entenderlo, ese no es un buen ejemplo pedagógico. (Y la sabiduría de Norm Schryer se aplica).AB

Casi tan importante como esto es que utiliza un buffer temporal igual al tamaño de entrada, lo que es una implementación completamente impráctica. Queremos evitar microoptimizaciones confusas (como la conversión especial en mayúsculas de matrices pequeñas), pero el uso de un buffer temporal de tamaño realista tiene un efecto bastante fundamental en la forma en que se organiza el código. Quiere dar un ejemplo cuya estructura sea reconociblemente similar a una implementación práctica.

El código de la lista no estaba en tan mal estado, pero no me gustó cómo el código de la lista descendente y ascendente usaba abstracciones diferentes para las listas. Esas diferencias gratuitas hacen que sea difícil para el lector ver las diferencias significativas. Una cosa que hice específicamente fue usar las mismas Mergeoperaciones básicas en ambos ejemplos.

Estuve pensando un rato y creo que se me ocurrieron implementaciones bastante concisas y claras que no dejan de lado nada importante (se manejan casos especiales complicados como la entrada de tamaño cero). Pero dada la cantidad de discusión que ha tenido lugar aquí, probablemente debería haberlo propuesto aquí para su discusión en lugar de simplemente editarlo en el artículo. Ups.

Una cosa con la que no estoy contento y que todavía necesita ser corregida son los nombres de las funciones; las funciones de ordenación de matrices y listas tienen actualmente los mismos nombres. Afortunadamente, ese es un punto lo suficientemente menor como para que no haga daño significativo al artículo a la espera de una resolución. Tampoco estoy contento con la manipulación de bits confusa en la lsbit()función. La puse en su propia función y la comenté muchísimo, pero no puedo encontrar un artículo existente al que vincular.

Otro problema que necesita ser corregido es que la descripción de la fusión basada en cintas hace referencia al código de ejemplo ascendente, pero el código de ejemplo (tanto antes como después de mi reescritura) utiliza un orden de fusión en profundidad. La fusión en cintas opera en amplitud. Al menos agregué algunas palabras sobre la diferencia (corté antes de desviarme hacia fusiones multidireccionales con reconocimiento de caché), pero la referencia a la fusión en cintas necesita ser corregida. Actualización: He corregido esto.

De todos modos, lo siento por soltar una bomba en el artículo. Estoy acostumbrado a editar artículos tranquilos en los que la página de discusión está repleta de comentarios y pedir comentarios allí es un proceso que lleva meses. Así que es WP:BOLD o irse a casa. Debería haber revisado este primero. 196.247.24.22 ( discusión ) 00:50, 22 de diciembre de 2019 (UTC) [ responder ]

Vale, ya ha pasado un mes sin ningún tipo de comentario. Supongo que no tenía por qué preocuparme tanto. 196.247.24.22 ( discusión ) 22:42 22 ene 2020 (UTC) [ responder ]

El motivo de que no haya comentarios probablemente se deba a que ha pasado aproximadamente un año desde el último cambio en el pseudocódigo y algunos de los miembros no esperaban ningún cambio y no estaban monitoreando el artículo. Yo estaba ausente u ocupado con otros proyectos y me perdí los cambios que se hicieron. Basándome en discusiones anteriores sobre esto, aquí y en las páginas de discusión de otros miembros, revertí los ejemplos a su estado anterior. No soy partidario de la mezcla entre el ordenamiento de arriba hacia abajo y el de abajo hacia arriba para los ejemplos de listas enlazadas, pero las discusiones anteriores querían que el ordenamiento de arriba hacia abajo se dejara solo. Tal vez ahora sea el momento de revisar esto, pero tendré que contactar de alguna manera a los miembros anteriores involucrados en esto. Agregué una explicación sobre cómo funciona el ordenamiento de arriba hacia abajo para la combinación de matrices. Regístrese para obtener una cuenta Wiki para que tenga una página de discusión que proporcione un medio para que otros se comuniquen con usted. Rcgldr ( discusión ) 16:27, 3 de febrero de 2020 (UTC) [ responder ]

Su código (de Special:Permalink/931876827#Implementación de arriba hacia abajo ) parece incorrecto. Parece que si se le suministra una matriz de dos elementos, {0, 1}devolverá {1, 0}el resultado. -- CiaPan ( discusión ) 10:12 4 feb 2020 (UTC) [ responder ]

@ CiaPan : Para otros que lean esto, Ciapan se refiere a una edición anterior del usuario:196.247.24.22 que se deshizo y volvió a una versión funcional conocida: Special:Permalink/938979353#Implementación de arriba hacia abajo Rcgldr ( discusión ) 15:12, 4 de febrero de 2020 (UTC) [ responder ]

Así es, lamento expresarme de manera tan ambigua.
Gracias, Rcgldr , por explicar las cosas. -- CiaPan ( discusión ) 15:51 4 feb 2020 (UTC) [ responder ]

Corrección de errores menores

Dejo una nota aquí porque, obviamente, se ha hecho mucho trabajo, pero el cambio que estoy haciendo es bastante menor. He pasado por alto la discusión más reciente en particular y no creo que me haya perdido ninguna discusión sobre esto, pero, por supuesto, podría estar equivocado.

Al realizar una implementación, noté un error de uno en uno: al verificar el tamaño uno, la diferencia de los índices se compara con 2. Pero creo que los índices son inclusivos, por lo que si tenemos, por ejemplo, 0 y 1, la diferencia es 1 pero el tamaño es 2. Creo que este error se introdujo al pasar de una función que verificaba la longitud a usar índices de matriz donde se calcula, pero no he verificado el historial para confirmarlo.

Entonces, voy a cambiar el valor allí de 2 a 1, ya que creo que es la comparación correcta (es decir: si ba < 1, entonces tenemos 1 (o menos) elementos y no necesitamos dividir/fusionar).

Écrivan renaissant (discusión) 06:28, 17 de julio de 2020 (UTC) [ respuesta ]

@Écrivan renaissant: En cuanto a:

Pero los índices son inclusivos, creo.

Yo diría que normalmente es mejor saber que creer.

Y el comentario justo encima de la función TopDownSplitMergeque modificaste explícitamente dice:

// Ordena la ejecución dada de la matriz A[] usando la matriz B[] como fuente. // iBegin es inclusivo; iEnd es exclusivo (A[iEnd] no está en el conjunto).

Por favor revierta su cambio. -- CiaPan ( discusión ) 13:54 22 jul 2020 (UTC) [ responder ]

@Écrivan renaissant: Otro editor arregló eso: special:diff/968920370 . -- CiaPan ( discusión ) 20:30 5 ago 2020 (UTC) [ responder ]

Referencia incompleta

En la subsección Uso con unidades de cinta , parece haber una referencia incompleta (actualmente nota 11):

<ref>Ordenamiento por selección. Quitanieves de Knuth. Fusión natural.</ref>

-- Mortense ( discusión ) 21:00 20 nov 2020 (UTC) [ responder ]

@ Mortense : Esto fue agregado por Glrx en esta edición Especial:Diff/471918025 el 17 de enero de 2012.

Glrx no está muy activo estos días, por lo que no esperaría una respuesta rápida de ellos, pero, ¿quién sabe...? -- CiaPan ( discusión ) 00:20 22 nov 2020 (UTC) [ responder ]

@ Mortense : La misma expresión aparece en una cita más detallada:

Donald Knuth , El arte de la programación informática , Ordenación y búsqueda, Volumen 3, 1973. El argumento del "quitanieves". p. 254

en el artículo de clasificación de torneos , sección #Aplicación común . Esto también lo agregó Glrx en Special:Diff/341048803 el 31 de enero de 2010 y se amplió (al agregar el "quitanieves") en Special:Diff/426315622 el 28 de abril de 2011. -- CiaPan ( discusión ) 00:33 22 nov 2020 (UTC) [ responder ]

No tengo acceso a El arte de la programación en este momento , pero encontré una descripción bastante precisa del arado aquí:

URL: http://didawiki.cli.di.unipi.it/lib/exe/fetch.php/magistraleinformatica/ir/ir10/notes.pdf

Autor: Paolo Ferragina

Título: desconocido

Capítulo: 4

Título del capítulo: Ordenación de elementos atómicos

Páginas: 4-4 y siguientes

HTH. -- CiaPan ( discusión ) 00:53 22 nov 2020 (UTC) [ responder ]

@Mortense y Glrx : Por fin he añadido la referencia: Special: Diff /1022865342 . Más vale tarde que nunca. CiaPan ( discusión ) 23:30 12 may 2021 (UTC) [ responder ]

¿La clasificación por fusión está inspirada en las alzadoras de tarjetas perforadas?

Por ejemplo, una de las operaciones de la clasificadora de tarjetas perforadas IBM 077 de 1937 era fusionar dos barajas de tarjetas ya ordenadas. También podía eliminar duplicados. Sin embargo, no he podido averiguar si la ordenación por combinación se inspiró en la operación de fusión de dichas clasificadoras. Rcgldr ( discusión ) 18:09 12 may 2021 (UTC) [ responder ]

@ Rcgldr : Se dan algunas sugerencias sobre la fuente en el hilo ¿ Cómo se le ocurrió a Von Neumann su algoritmo Merge Sort? en el sitio StackExchange 'Historia de la ciencia y las matemáticas':

https://hsm.stackexchange.com/questions/12549/how-did-von-neumann-come-up-with-his-merge-sort-algorithm

Este hilo en Quora también parece relevante (pero no lo leí): ¿Cómo descubrió Von Neumann la ordenación por fusión? ¿Hubo algún predecesor de la ordenación por fusión?

https://www.quora.com/How-did-Von-Neumann-discover-the-merge-sort-Was-there-any-predecessor-to-the-merge-sort

CiaPan ( discusión ) 21:50 12 may 2021 (UTC) [ responder ]

El análisis del número de comparaciones en el peor de los casos es incorrecto

El análisis del número T de comparaciones de claves en el peor de los casos realizado mediante la ordenación por combinación es incorrecto.

Comienza a partir de una relación de recurrencia incorrecta

${\displaystyle T(n)=2T(n/2)+n.}$

En primer lugar, la relación de recurrencia mencionada es diferente para el peor caso, el caso promedio y el mejor caso. En segundo lugar, es formalmente inválida, excepto para los casos en que n es una potencia de 2 (porque T requiere argumentos enteros y n/2 no es un entero si n es impar). En tercer lugar, maneja mal el caso base de n = 1. Y la referencia ^[1] que se supone que la justifica es inválida porque no la implica. [Esta oración fue agregada por MA Suchenek ( discusión ) 20:14, 8 de junio de 2021 (UTC).] [ responder ]

La relación de recurrencia correcta para el número de comparaciones de claves en el peor de los casos realizadas mediante la ordenación por combinación en n elementos distintos es ${\displaystyle T_{worst}}$

${\displaystyle T_{worst}(n)=T_{worst}(\lfloor n/2\rfloor )+T_{worst}(\lceil n/2\rceil )+n-1}$para y ${\displaystyle n\geq 2}$

${\displaystyle T_{worst}(1)=0.}$

Como mencioné antes, la matriz de n elementos no se puede dividir en dos submatrices de igual tamaño n/2 si n es impar, simplemente porque una matriz no puede tener un tamaño que no sea un número entero. Por ejemplo, si n = 3, entonces la matriz se divide en dos submatrices de tamaños y , y no en dos matrices de tamaño 1,5. ${\displaystyle \lfloor 3/2\rfloor =1}$ ${\displaystyle \lceil 3/2\rceil =2}$

Además, el número de comparaciones de claves en el peor de los casos al fusionar dos listas ordenadas de tamaño total n es n-1 y no n. Por ejemplo, fusionar dos listas de 1 elemento (y, por lo tanto, tener un total de 2 elementos) requiere 1 comparación de claves y no 2 comparaciones.

El comentario de que el análisis de Knuth es incorrecto porque supuestamente Knuth utilizó una versión "ligeramente subóptima" de Merge sort quedó sin explicación. Como resultado, no queda claro qué Merge sort se está analizando en la sección "Análisis". La versión estándar de Merge sort que satisface la relación de recurrencia estándar (dada anteriormente) para tiene exactamente el peor desempeño posible (y no "ligeramente" mejor que) dado por Knuth. MA Suchenek ( discusión ) 21:18 1 jun 2021 (UTC) [ responder ] ${\displaystyle T_{worst}}$

Vale, pero necesitaríamos una fuente que cumpla las pautas de Wikipedia para poder hacer algo con esto. Los artículos preimpresos (especialmente los que has escrito tú mismo) no cumplen ese requisito. Véase también Wikipedia:No original research - MrOllie ( discusión ) 01:40, 2 de junio de 2021 (UTC) [ responder ]

La regla es la verdad, sobre todo si se ha demostrado, y no cómo se publicó. Las referencias y citas de arxiv.org no son "investigación original". Por un lado, eliminaste material fáctico que tiene pruebas elementales y fáciles de verificar en el material al que se hace referencia, mientras que, por otro lado, mantienes declaraciones sin fundamento o falsas (como que la fórmula de Knuth era incorrecta) sin referencia a ninguna fuente, en absoluto. Tal vez, ¿podrías considerar cumplir con tus propios estándares? MA Suchenek ( discusión ) 08:56, 2 de junio de 2021 (UTC) [ responder ]

MA Suchenek, no, eso es lo opuesto a cómo funciona Wikipedia. Véase Wikipedia:Verificabilidad, no verdad . Le recomiendo que lea WP:NOR y WP:RS . Las preimpresiones de arxiv.org no tienen absolutamente ningún control editorial. Según la filosofía que usted defiende aquí, cualquiera podría escribir cualquier cosa, subirla a arxiv y luego usarla como fuente. La existencia de otro contenido con fuentes incorrectas es una razón para corregir ese contenido, no para agregar más contenido con fuentes incorrectas. Especialmente no cuando tiene un conflicto de intereses con la fuente que está agregando. - MrOllie ( discusión ) 11:50, 2 de junio de 2021 (UTC) [ responder ]

Estás equivocado. Mira más abajo. Además, las referencias que insertaste en el artículo, sección Análisis, son irrelevantes ya que no respaldan las afirmaciones falsas que quedaron sin referencias en su versión anterior . MA Suchenek ( discusión ) 20:14 8 jun 2021 (UTC) [ responder ]

Argumento autocontradictorio, afirmación absurda, etc.

MrOllie : Su argumento (arriba) es contradictorio y, por lo tanto, inválido.

En primer lugar, eliminaste mi inserción de material relevante con pruebas publicadas, alegando que la referencia no era "fiable". Luego justificaste la eliminación con una referencia a la página Wikipedia:Verificabilidad, no verdad , que en sí misma no es confiable, no se puede verificar y, de hecho, incluye consejos y opiniones de algunas personas de credibilidad desconocida, como lo indica claramente la siguiente cita (con énfasis añadido) de la parte superior de esa página Wikipedia:Verificabilidad, no verdad :

"Este es un ensayo sobre las políticas de verificabilidad.

Contiene los consejos u opiniones de uno o más colaboradores de Wikipedia . Esta página no es un artículo de enciclopedia ni forma parte de las políticas o pautas de Wikipedia, ya que no ha sido revisada exhaustivamente por la comunidad . Algunos ensayos representan normas generalizadas; otros solo representan puntos de vista minoritarios .

Continuó justificando la eliminación de mi adición señalando la página de Wikipedia WP:NOR "Sin investigación original", mientras que todo el artículo que agregué tiene una exención de responsabilidad en la parte superior que dice:

" Es posible que este artículo contenga investigaciones originales . Por favor, mejórelo verificando las afirmaciones realizadas y agregando citas en línea. Las afirmaciones que consistan únicamente en investigaciones originales deben eliminarse ". (Énfasis añadido).

Así que no pasas tus propios estándares que estás tratando de imponerme.

Luego sigues afirmando que la veracidad demostrada de mi inserción no importa porque su prueba publicada no proviene de una referencia "fiable". Esta afirmación tuya de que la verdad es secundaria a la credibilidad del instrumento de su publicación no es sólo absurda; va en contra de la metodología dominante de la ciencia moderna y, en particular, de las matemáticas. La fórmula exacta para el mejor desempeño de Merge sort tiene una prueba publicada (en arxiv.org ^[2] ) que es verificable por cualquier persona con suficiente preparación universitaria en matemáticas y suficiente coeficiente intelectual. Eliminarla fue un acto de supresión de conocimiento objetivo (y verificable) bajo la doctrina de que proviene de una fuente no aprobada por ti. Tal acción cae en la categoría de censura.

Además, aparentemente utilizas un doble estándar para determinar qué material es adecuado para su inclusión en las páginas de Wikipedia y cuál no. Por un lado, eliminaste material objetivamente verdadero que publiqué, a pesar de que tiene una prueba publicada ^[2] , pero al mismo tiempo permitiste que la información falsa en la misma sección del artículo (como indiqué anteriormente) permaneciera incluida a pesar de que no tiene ninguna referencia relevante a ninguna fuente creíble que la valide, y a pesar de la instrucción en la parte superior del artículo (citada anteriormente) de que dicha información debe eliminarse. Entonces, cuando se trata de declaraciones obviamente falsas en el artículo, como una afirmación (con una referencia mayoritariamente irrelevante) de que la relación de recurrencia para la ordenación por combinación es:

${\displaystyle T(n)=2T(n/2)+n}$

o el comentario (con una referencia irrelevante) de que el análisis de Knuth es incorrecto porque Knuth supuestamente utilizó una versión "ligeramente subóptima" de Merge sort (declaración que contradice la definición estándar de Merge sort que se caracteriza por la relación de recurrencia (ver ^[3] )

${\displaystyle T_{worst}(n)=T_{worst}(\lfloor n/2\rfloor )+T_{worst}(\lceil n/2\rceil )+n-1}$para ${\displaystyle n\geq 2}$

y

${\displaystyle T_{worst}(1)=0}$)

eres ajeno a que no solo carecen de referencias sino que son falsas, y sin embargo te das el mandato de eliminar mi aportación porque la referencia con prueba verificable que proporcioné ^[2] no cumple con tu absurdo estándar de credibilidad de la fuente.

Una vez más, no obedeces los mismos estándares que esperas que sigan los demás. Me pregunto de dónde viene tu "autoridad" para imponer esos estándares a los demás y al mismo tiempo eximirte de ellos.

Su comentario sobre mi "conflicto de intereses" no es sólo una acusación no probada, sino que es completamente absurdo. (Supongo que no entiende cuál es el significado legal del término "conflicto de intereses"). Su comentario equivocado implica que de alguna manera no se me permite (¿con qué autoridad?) hacer referencia a pruebas que he elaborado y publicado ^[2] . Basándome en el doble rasero que ha exhibido en esta discusión y en su evidente sesgo que favorece las declaraciones falsas de su agrado por sobre las declaraciones demostrablemente verdaderas que usted rechaza, supongo que su acusación de "conflicto de intereses" es una proyección psicológica .

Su comentario sobre que cualquiera puede publicar cualquier cosa en arxiv.com es falso, ya que es irrelevante. Porque una prueba es una prueba sin importar cómo se haya publicado, siempre y cuando se haya publicado de una manera que permita un acceso público estable y sin restricciones.

Debido a sus acciones equivocadas, el artículo Merge sort, sección Análisis, es de calidad deficiente.

MA Suchenek ( charla ) 20:14, 8 de junio de 2021 (UTC) [ respuesta ]

MA Suchenek, consulta WP:COI , cuyo enlace se ha incluido en tu página de discusión de usuarios durante aproximadamente una semana. Los significados legales no tienen nada que ver con esto (¿por qué lo tendrían?). Vincular tu propia preimpresión es absolutamente lo que la política COI de Wikipedia tiene en mente. No podemos obtener información de fuentes generadas por el usuario. Creo que llegarás mucho más lejos en Wikipedia si lees e intentas comprender las páginas de políticas que he estado vinculando en lugar de ignorarlas y llenar la página de discusión con irrelevancias. MrOllie ( discusión ) 20:32, 8 de junio de 2021 (UTC) [ responder ]

Sigues repitiendo tus absurdas acusaciones. Aquí tienes citas de WP:COI :

"La edición por conflicto de intereses (COI) implica contribuir a Wikipedia sobre usted mismo, su familia, sus amigos, sus clientes, sus empleadores o sus relaciones financieras y de otro tipo".

y

"Los editores con un COI, incluidos los editores pagos, deben revelarlo siempre que intenten cambiar el contenido de un artículo afectado. Cualquier persona que edite a cambio de un pago debe revelar quién le paga, quién es el cliente y cualquier otra afiliación relevante; este es un requisito de la Fundación Wikimedia".

No hay nada en el texto que sugiera que referirse a las propias pruebas publicadas de hechos matemáticos se considere un "conflicto de intereses". ¿Entiendes?

Sin duda tienes derecho a tener una opinión errónea, pero no tienes autoridad para decidir qué es o no es Wikipedia, ni para malinterpretar sus políticas.

En este foro, he desacreditado específicamente sus argumentos contradictorios y por lo demás inválidos que sigue repitiendo mientras el artículo (sección "Análisis") todavía contiene información errónea y referencias irrelevantes . Si esto es algo que le resulta demasiado difícil de entender, tal vez debería buscar algo más que hacer. MA Suchenek ( discusión ) 17:35 9 jun 2021 (UTC) [ responder ]

@MA Suchenek: Re No hay nada allí que sugiera que referirse a las propias pruebas publicadas de hechos matemáticos se considere "conflicto de intereses". ¿Entendido? - estás equivocado (y eres grosero, además). Citarse a uno mismo no siempre se considera conflicto de intereses, pero bien puede considerarse como tal, y la política lo dice explícitamente. Por favor, vea WP:SELFCITE . También puede considerarse autopromoción , que es una de las cosas que Wikipedia no es .

Por cierto, puede que hayas olvidado que, cuando señalas con el dedo a alguien, los otros tres dedos te señalan a ti mismo. Ten cuidado de no caer en el ámbito de tu último párrafo: si resolver un conflicto de manera educada, según las políticas de Wikipedia , es demasiado difícil para ti, entonces, tal vez, ................

CiaPan ( discusión ) 22:25 9 jun 2021 (UTC), no involucrado [ responder ]

@ CiaPan : Aquí hay una cita relevante de WP:SELFCITE :

"Se permite usar material que usted ha escrito o publicado dentro de lo razonable, pero sólo si es relevante, se ajusta a las políticas de contenido, incluidas WP:SELFPUB [fuentes autopublicadas], y no es excesivo" .

Mi autocita fue relevante, no violó las políticas de contenido y no fue excesiva.

Lo anterior hace que su insinuación y la de MrOllie de que mis ediciones violaban la política de Wikipedia sean una acusación absurda basada en opiniones y no respaldada por hechos.

Además, como ya he indicado antes, el "argumento" que se utilizó para justificar la supresión de la verdad matemática mediante la eliminación de mis ediciones fue un ejemplo de proyección psicológica : MrOllie me acusaba de utilizar fuentes "poco fiables" mientras basaba sus opiniones en lo que Wikipedia ha declarado claramente como fuentes no fiables. Ahora usted proyecta sobre mí su proyección, una táctica defensiva típica de alguien que se equivoca en cuanto a los hechos.

La diferencia entre usted y yo es sustancial: yo considero que la verdad matemática es el objetivo primordial y usted aparentemente no. Y si considera que señalarlo es "de mala educación", que así sea. Si es tan inteligente, siga adelante y busque un error matemático en el material elemental publicado y fácilmente disponible que cité (vea la sección "Material en disputa", más abajo) y en mi indicación detallada de errores en el artículo (vea el comienzo de la sección "El análisis del número de comparaciones en el peor de los casos es incorrecto", más arriba) en lugar de esconderse detrás de sus malas interpretaciones de la política de Wikipedia.

El resultado final es que sigues inventando cosas y recurriendo a opiniones no probadas y argumentos falaces, mientras que el artículo en cuestión todavía contiene información errónea en el capítulo "Análisis" (afirmaciones falsas y referencias irrelevantes que no las respaldan), como he indicado en detalle, pero parece que te es indiferente. Parece que tu principal objetivo aquí no es asegurar la veracidad de los artículos de Wikipedia, sino ganar una discusión independientemente de cuál sea la verdad. MA Suchenek ( discusión ) 17:14 20 jun 2021 (UTC) [ responder ]

MA Suchenek, como ya te he dicho varias veces, el uso de preprints de arxiv, de hecho, viola las políticas de contenido. MrOllie ( discusión ) 18:12 20 jun 2021 (UTC) [ responder ]

@ MrOllie : Te has equivocado en esto, como indiqué anteriormente. Por favor, muéstrame "políticas de contenido" específicas de Wikipedia (en contraposición a tu opinión o la de otra persona) que "el uso de preprints de arxiv sí viola" . MA Suchenek ( discusión ) 19:10 24 jun 2021 (UTC) [ responder ]

Material en disputa

Para que quede constancia, aquí está el cuerpo del inserto que fue eliminado:

La relación de recurrencia en el mejor número de comparaciones de claves realizadas mediante la ordenación por combinación en n elementos distintos viene dada por: ${\displaystyle T_{best}}$

${\displaystyle T_{best}(n)=T_{best}(\lfloor {\frac {n}{2}}\rfloor )+T_{best}(\lceil {\frac {n}{2}}\rceil )+\lfloor {\frac {n}{2}}\rfloor }$para , ${\displaystyle n\geq 2}$

y

${\displaystyle T_{best}(1)=0.}$

Para entenderlo, basta con observar que, en el mejor de los casos, cada elemento de la lista más corta de las dos fusionadas debe compararse con un elemento de la otra lista.

Resolver la relación de recurrencia anterior resulta bastante complicado y más complejo que resolver la relación de recurrencia para el peor de los casos. Se ha hecho, por ejemplo, en ^[2] :

${\displaystyle T_{best}(n)={\frac {n}{2}}(\lfloor \log _{2}n\rfloor +1)-\sum _{k=0}^{\lfloor \log _{2}n\rfloor }2^{k}Zigzag({\frac {n}{2^{k+1}}})}$

donde es una función real continua que oscila como un zigzag entre 0 y y viene dada por: ${\displaystyle Zigzag}$ ${\displaystyle {\frac {1}{2}}}$

${\displaystyle Zigzag(x)=min(x-\lfloor x\rfloor ,\lceil x\rceil -x)}$.

En particular, para n relativamente pequeño, es sustancialmente mayor que (o, en otras palabras, es sustancialmente mayor que la mitad de ), como lo muestra la siguiente desigualdad derivada para cualquier n en ^[2] : ${\displaystyle 2\times T_{best}(n)}$ ${\displaystyle T_{worst}(n)}$ ${\displaystyle T_{best}(n)}$ ${\displaystyle T_{worst}(n)}$

${\displaystyle {\frac {n-1}{2}}\leq 2\times T_{best}(n)-T_{worst}(n)\leq n-1}$.

A medida que n y , convergen a ∞, la relación entre la diferencia anterior y converge a cero, es decir, para un n grande, es aproximadamente igual a, aunque mayor que, la mitad de ${\displaystyle log_{2}n}$ ${\displaystyle T_{best}(n)}$ ${\displaystyle T_{best}(n)}$ ${\displaystyle T_{worst}(n).}$

Referencias

Referencias

1. Cormen y otros (2009, pág. 36) harvtxt error: no target: CITEREFCormenLeisersonRivestStein2009 (help)
2. Suchenek, MA, "Análisis del mejor caso de MergeSort con una aplicación al problema de suma de dígitos", https://arxiv.org/pdf/1607.04604v1.pdf
3. Suchenek MA>, "Análisis elemental pero preciso del peor caso de MergeSort", https://arxiv.org/pdf/1702.08443.pdf

Me encontré por casualidad con la etiqueta OR. Estoy de acuerdo con MrOllie. No puedes usar tu propia investigación no publicada como cita aquí. Citaría la política wiki pertinente, pero MrOllie ya lo hizo. Stix1776 ( discusión ) 10:59 23 jun 2022 (UTC) [ responder ]

posible error

Soy nuevo en C++ y en la edición de Wikipedia (he estado perdiendo el sueño tratando de encontrar estos errores), por lo que no tengo la confianza para hacer esta edición: creo que hay un error en TopDownMerge, la primera declaración if creo que no debería leerse.

 si (i < iMedio && (j >= iFin || A[i] <= A[j])) {

pero

 si (i <= iMedio && (j > iFin || A[i] <= A[j])) {

Razonamiento: si la matriz tiene 2 elementos, i(0) será igual a iMiddle(0) y j(1) será igual a iEnd(1). En la primera pasada, la primera declaración será verdadera y la segunda será falsa. El tamaño de cada elemento determina cuál se copia primero en la otra matriz.

Rthepb (discusión) 14:42 25 nov 2021 (UTC) [ responder ]

@Rthepb: Eso está mal. Cuando la matriz tiene dos elementos, iBegin es igual a 0, iMiddle es igual a 1 y iEnd es igual a 2. -- CiaPan ( discusión ) 21:50, 26 de noviembre de 2021 (UTC) [ responder ]

combinación de ping pong

¿Es necesaria esta sección o debería mencionarse que la mayoría de las implementaciones de ordenamiento por fusión ya incorporan un concepto similar? El ejemplo de ordenamiento por fusión de arriba hacia abajo (para matrices) evita la copia inversa cambiando la dirección de la fusión para cada nivel de recursión (realiza una copia inicial, pero se pueden usar funciones recursivas mutuas para evitar la copia inicial). El ejemplo de ordenamiento por fusión de abajo hacia arriba menciona esto en un comentario que dice que intercambiar punteros evitaría el bucle de copia inversa que se muestra. Los dos primeros pasos de un ordenamiento por fusión de abajo hacia arriba son el equivalente a un ordenamiento por fusión de ping pong. La dirección alterna de las operaciones de fusión para el ordenamiento por fusión se remonta a principios de los años 60 (o antes) para los ordenamientos de cinta que utilizan ordenamiento por fusión o ordenamiento por fusión polifásico. Rcgldr ( discusión ) 18:34, 10 de enero de 2023 (UTC) [ responder ]

Una fusión ping-pong implica la fusión de 4 segmentos a la vez, lo que a su vez permite el paralelismo en las arquitecturas modernas. No habría tenido sentido en los años 60. En los próximos años deberían estar disponibles mejores fuentes sobre el tema y supongo que se referirán a ello como fusión ping-pong. Yugodocs ( discusión ) 14:11 15 ene 2023 (UTC) [ responder ]

@Yugodocs: - el paralelismo es típicamente más genérico. Digamos que hay 8 núcleos disponibles. La matriz que se va a ordenar se divide en 8 partes iguales (o casi). Cada una de las 8 partes se ordena (supongamos que mediante ordenación por fusión). Después de que las 8 partes se ordenan en 8 ejecuciones ordenadas, se utilizan 4 núcleos para fusionar 4 pares de ejecuciones ordenadas en 4 ejecuciones ordenadas, se utilizan 2 núcleos para fusionar 2 pares de ejecuciones ordenadas en 2 ejecuciones ordenadas, se utiliza 1 núcleo para fusionar 1 par de ejecuciones ordenadas en la ejecución ordenada final. Ejemplo de una ordenación por fusión multiproceso de Windows, esta de 2016. Mi primera versión fue alrededor de 2012, cuando compré mi primer escritorio de 4 núcleos. Los mainframes de IBM que datan de fines de la década de 1960 admitían multitarea real, pero no sé cuándo se implementó la primera ordenación por fusión multiproceso en un mainframe de IBM. Sort (Unix) lanzado por primera vez en 1971, tiene como valor predeterminado 16 subprocesos para la fase inicial de ordenación por fusión de memoria interna (lee un grupo de registros, crea y utiliza una ordenación multiproceso para ordenar una matriz de punteros a registros, luego escribe los registros de acuerdo con la matriz para crear ejecuciones ordenadas), luego tiene como valor predeterminado una fusión de 16 vías de un solo subproceso para las fases de fusión externas. El código fuente de Github para Sort muestra una fecha de 1988, no sé dónde están archivadas las versiones anteriores. Rcgldr ( discusión ) 19:56, 15 de enero de 2023 (UTC) [ responder ]

Me refería al paralelismo a nivel de instrucción y al paralelismo a nivel de memoria . El autor de pdqsort mencionó el primero, mientras que el autor de quadsort mencionó el segundo. No está relacionado con el multihilo hasta donde yo sé. Yugodocs ( discusión ) 01:11, 16 de enero de 2023 (UTC) [ responder ]

@Yugodocs: Al hacer una búsqueda en la web sobre la combinación de ping pong, encontré un artículo de Microsoft sobre mejoras en Patience sort , al que llaman Patience+. El objetivo de ese artículo es cómo mejorar Patience sort, que se basa en el juego de cartas Patience del Reino Unido, similar al juego de cartas Solitaire de EE. UU. La combinación de ping pong combinará todas las ejecuciones ordenadas (no solo 4) en un contenedor alternativo y luego volverá a combinarlas con el contenedor original en la siguiente pasada. Las combinaciones de ordenamiento han estado utilizando la combinación de ping pong desde los años 60. La implementación original de Patience sort no utilizaba la combinación de ping pong y esa fue una de las mejoras. La combinación de Patience sort mejorada, llamada Patience+, es principalmente útil para ordenar datos casi ordenados. No conozco ninguna biblioteca estándar (como C++ std::sort o std::stable_sort o std::list::sort) que la implemente. Rcgldr ( discusión ) 19:35 17 ene 2023 (UTC) [ responder ]

@Yugodocs: - pdqsort es un patrón que derrota a quicksort. quadsort es una versión de más de 1000 líneas (.h + .c) de ordenación por fusión con muchas optimizaciones. El autor la compara con alguna versión de std::stable_sort() de C++, que normalmente no está tan optimizada. La implementación de std::stable_sort de Dinkumware | HP | Microsoft se basa en el código de 1994, por defecto asigna una matriz temporal de la mitad del tamaño (o menor) de la matriz de origen, siempre utiliza un puntero a la función de comparación, no hay optimización para establecer el tamaño de las ejecuciones creadas por ordenación por inserción, ..., lo que afecta al rendimiento. Utiliza la ordenación por inserción para crear ejecuciones ordenadas de 32 elementos, luego cambia a la ordenación por fusión de abajo a arriba. Volviendo al punto principal, las ordenaciones por fusión tradicionales han hecho el equivalente a la fusión de ping pong desde los años 60. Rcgldr ( discusión ) 18:43 18 ene 2023 (UTC) [ responder ]

En ese caso, la sección debería agregar una mención a una ordenación de fusión temprana que incorpore una fusión de ping pong.

@Yugodocs: Este artículo de Wiki ya lo hace: Merge_sort#Use_with_tape_drives ... IBM 729 (finales de los años 50). Esto también se menciona en quadsort github en Créditos: "La combinación ping-pong se había implementado de forma independiente en wikisort antes de quadsort, y probablemente también por otros". Rcgldr ( discusión ) 13:29 19 ene 2023 (UTC) [ responder ]

El paralelismo a nivel de memoria de la fusión cuádruple parece notable, la fusión sin ramificaciones pareada que el autor menciona en el artículo sobre la ordenación cuádruple. También está este artículo: https://www.researchgate.net/publication/255567817_Branch_Mispredictions_Don't_Affect_Mergesort

Definitivamente, hay una mejora de rendimiento cercana al 100 % para quadsort en comparación con std::stable_sort, que el autor atribuye a la combinación de una fusión sin ramificaciones con la escritura en dos regiones de memoria en el mismo bucle, y algo sobre el desenrollado del bucle. Yugodocs ( discusión ) 19:46, 18 de enero de 2023 (UTC) [ responder ]

@Yugodocs: - Convertí quadsort para compilar con Visual Studio (VS no permite devolver void), y lo comparé con mis programas genéricos de ordenación por inserción híbrida | ordenación por combinación, y se ejecuta entre 1,5 (computadora de escritorio Intel 3770K) y casi 2,0 veces más rápido (computadora portátil Intel 10510U) con datos pseudoaleatorios, pero 1,6 veces más lento en el caso inusual de muchos duplicados. No estoy seguro de por qué el caso duplicado es un problema, para una ordenación por combinación típica, es similar a los datos ya ordenados, donde el número de comparaciones es aproximadamente n/2 en lugar de n-1, y solo (1 en n/2) predicciones erróneas de bifurcación. quadsort es muy rápido con datos ya ordenados, por lo que probablemente solo necesite algo de optimización adicional para duplicados. Son 1000 líneas de código con muchas optimizaciones, la mayoría de las cuales reducen el número de comparaciones, algunas de las cuales reducen el número de movimientos. Scandum menciona que la paridad sin ramificaciones y las fusiones galopantes que operan desde ambos extremos de una matriz son las optimizaciones clave, aunque el resto de las optimizaciones contribuyen al rendimiento. Rcgldr ( discusión ) 03:20 23 ene 2023 (UTC) [ responder ]

Orden de complejidad de la ordenación por combinación

El peor caso de complejidad temporal para este algoritmo es n*lg(n) según Introducción a los algoritmos . No n*log(n) como se indica en la sección Análisis. --Siavoshkc ( discusión ) 17:22 24 sep 2023 (UTC) [ responder ]

@Siavoshkc: Son lo mismo. Cambiar la base de un logaritmo equivale a multiplicarlo por algún factor constante, y los factores constantes no tienen sentido en el orden de complejidad. -- CiaPan ( discusión ) 19:06 24 sep 2023 (UTC) [ responder ]

¡Gracias! Me estuvo dando vueltas en la cabeza por un tiempo. Siavoshkc ( discusión ) 08:11 7 nov 2023 (UTC) [ responder ]

Ordenación por combinación recursiva para listas doblemente enlazadas: no es necesario escanear listas para dividir sublistas

En lugar de escanear listas para dividirlas por la mitad, un valor entero del tamaño de la lista se divide por 2 para cada nivel de recursión, hasta un caso base donde el tamaño == 1, donde se devuelve un puntero | iterador al siguiente nodo. La ordenación por combinación recursiva actualiza (pasa por referencia) un puntero | iterador al nodo inicial y devuelve un puntero | iterador al nodo final de una lista ordenada. Visual Studio 2022 cambió a este método para std::list::sort. El siguiente es un ejemplo de C++ que utiliza iteradores. Nombres de iterador: li = iterador de ejecución izquierda, ri = iterador de ejecución derecha = iterador de ejecución izquierda final, ei = iterador de ejecución derecha final. La combinación empalmará (moverá e insertará) sublistas (múltiples nodos) de ejecución derecha a ejecución izquierda para valores de ejecución derecha < valor de ejecución izquierda actual, de lo contrario, solo avanza el iterador de ejecución izquierda. La empalme requiere una lista doblemente enlazada.

plantilla <typename T>tiponombre std::list<T>::iterador Merge(std::list<T> &ll, tiponombre std::list<T>::iterador li, tiponombre std::list<T>::iterador ri, tiponombre std::list<T>::iterador ei){ std::list<T>::iterator si; std::list<T>::iterador ni; ni = (*ri < *li) ? ri : li; mientras(1){ si(*ri < *li){ for(si = std::next(ri); si != ei && *si < *li; si++); ll.splice(li, ll, ri, si); ri = si; si(ri == ei) devuelve ni; } demás { si (++li == ri) devuelve ni; } }}plantilla <typename T>tiponombre std::list<T>::iterador SortListR(std::list<T> &ll, tiponombre std::list<T>::iterador &li, tamaño_t tamaño){ si (tamaño == 1) devolver std::next(li); std::list<T>::iterador ri; std::list<T>::iterador ei; ri = SortListR(ll, li, tamaño-tamaño/2); ei = SortListR(ll, ri, tamaño/2); li = Fusionar(ll, li, ri, ei); devuelve ei;}plantilla <typename T>vacío SortList(std::list<T> &ll){ if (ll.size() < 2) // retorna si no hay nada que hacer devolver; SortListR(ll, ll.begin(), ll.size());}

Rcgldr ( discusión ) 02:14 24 abr 2024 (UTC) [ responder ]