Agregar elementos a una matriz ordenada

¿Cuál sería la forma más rápida de hacer esto (desde una perspectiva algorítmica, así como una cuestión práctica)?

Estaba pensando algo en las siguientes líneas.

Podría agregar al final de una matriz y luego usar bubbleort, ya que tiene un mejor caso (matriz totalmente ordenada al inicio) que está cerca de esto, y tiene un tiempo de ejecución lineal (en el mejor de los casos).

Por otro lado, si sé que empiezo con una matriz ordenada, puedo usar una búsqueda binaria para encontrar el punto de inserción de un elemento dado.

Mi presentimiento es que la segunda forma es casi óptima, pero curiosa por ver qué hay ahí fuera.

¿Cómo se puede hacer esto mejor?

Contamos el número de lecturas y escrituras de elementos de matriz. Para hacer el ordenamiento de burbujas, necesita accesos (la escritura inicial hasta el final, luego, en el peor de los casos, dos lecturas y dos escrituras para hacer swaps). Para hacer la búsqueda binaria, necesitamos ( para búsqueda binaria, luego, en el peor de los casos, para desplazar los elementos de la matriz a la derecha, luego 1 para escribir el elemento de la matriz en su posición correcta).$1 + 4n$$n$$2\log n + 2n + 1$$2\log n$$2n$

Entonces, ambos métodos tienen la misma complejidad para las implementaciones de matrices, pero el método de búsqueda binaria requiere menos accesos a la matriz a largo plazo ... asintóticamente, la mitad. Hay otros factores en juego, naturalmente.

En realidad, podría usar mejores implementaciones y solo contar los accesos a la matriz real (no los accesos al elemento que se va a insertar). Podría hacer para ordenar burbujas, y para búsqueda binaria ... así que si el acceso al registro / caché es barato y el acceso a la matriz es costoso, busque desde el final y cambie en el camino (burbuja más inteligente ordenar para la inserción) podría ser mejor, aunque no asintóticamente.$2n + 1$$\log n + 2n + 1$

Una mejor solución podría implicar el uso de una estructura de datos diferente. Las matrices le dan acceso O (1) (acceso aleatorio), pero las inserciones y eliminaciones pueden costar. Una tabla hash podría tener O (1) inserciones y eliminaciones, los accesos costarían. Otras opciones incluyen BST y montones, etc. Podría valer la pena considerar las necesidades de uso de su aplicación para inserción, eliminación y acceso, y elegir una estructura más especializada.

Tenga en cuenta también que si desea agregar elementos a una matriz ordenada de elementos, una buena idea podría ser ordenar eficientemente los elementos , luego fusionar las dos matrices; Además, las matrices ordenadas se pueden construir de manera eficiente utilizando, por ejemplo, montones (clasificación de montón).$m$$n$$m$

Si tiene alguna razón para no usar el montón, considere usar el método de inserción en lugar del método de burbuja. Es mejor cuando tienes algunos elementos sin clasificar.

Debido a que está utilizando una matriz, le cuesta insertar un elemento; cuando agrega algo al centro de una matriz, por ejemplo, tiene que cambiar todos los elementos después de uno para que la matriz permanezca ordenada .$O(n)$

La forma más rápida de averiguar dónde colocar el elemento es como mencionó, una búsqueda binaria, que es , por lo que la complejidad total será O ( n + lg n ) , que está en el orden de O ( n ) .$O(\lg n)$$O(n + \lg n)$$O(n)$

$O(1)$

De todos modos, no veo ninguna razón para sacar la burbuja de este problema.

Patrick87 explicó todo esto muy bien. Pero una optimización adicional que podría hacer sería usar algo como un búfer circular: puede mover elementos a la derecha de la posición del elemento insertado a la derecha, como de costumbre. Pero también puede mover elementos a la izquierda de la posición correcta a la izquierda. Para hacer esto, debe tratar la matriz como circular, es decir, el último elemento está justo antes del primero y también requiere que mantenga el índice donde los elementos comienzan actualmente.

Si hace esto, podría significar que obtiene aproximadamente la mitad de los accesos a la matriz (suponiendo una distribución uniforme de los índices en los que inserta). En el caso de hacer una búsqueda binaria para encontrar la posición, es trivial elegir si se desplaza hacia la izquierda o hacia la derecha. En el caso de la clasificación de burbujas, debe "adivinar" correctamente antes de comenzar. Pero hacer eso es simple: simplemente compare el elemento insertado con la mediana de la matriz, que se puede hacer en acceso de matriz única.

He utilizado el algoritmo de clasificación de inserción de manera efectiva para este problema. En un momento tuvimos un problema de rendimiento con un objeto de tabla hash, escribí un nuevo objeto que utilizaba la búsqueda binaria en su lugar que aumentaba significativamente el rendimiento. Para mantener la lista ordenada, realizaría un seguimiento de la cantidad de elementos agregados desde la última clasificación (es decir, la cantidad de elementos sin clasificar) cuando la lista necesitaba ser ordenada debido a una solicitud de búsqueda, realizó una clasificación de inserción o una clasificación rápida dependiendo en el porcentaje de artículos sin clasificar. El uso del tipo de inserción fue clave para mejorar el rendimiento.