Tengo un conjunto de datos que es una serie de objetos dispuestos en una cuadrícula 2D. Sé que tengo un orden estricto, aumentando a medida que avanza de izquierda a derecha dentro de cada fila, y aumentando de arriba a abajo dentro de cada columna. Por ejemplo,
- 1 2 3
- 4 6 7
- 5 8 9
¿Puedo mejorar la ordenación ingenua para ordenar todo el conjunto de datos linealmente (como se mide en las comparaciones)?
¿Qué pasa con los conjuntos de datos nd? Conjuntos de datos finitos arbitrarios con un subconjunto de comparaciones conocidas?
ds.algorithms
total-ordering
sorting
Zachary Vance
fuente
fuente
Respuestas:
Es fácil demostrar un límite inferior de Ω (n 2 log n) en este problema (en el modelo de clasificación de comparación): si el elemento en la posición (i, j) está siempre dentro de la distancia 1/2 de i + j, entonces la cuadrícula las diagonales son independientes entre sí, y el orden ordenado dentro de cada diagonal de la cuadrícula es arbitrario. Entonces, bajo esta restricción, el número total de ordenamientos posibles es el producto (sobre todas las diagonales de la cuadrícula) de los factoriales de las longitudes de las diagonales, que es exponencial en n 2 log n.
Es decir que los algoritmos de clasificación de comparación estándar son asintóticamente óptimos para las cuadrículas ordenadas como usted describe.
fuente
Si entiendo el problema correctamente (y puede que no, siéntete libre de decirme si no lo hago) ¿quieres transformar una cuadrícula 2D en una matriz ordenada 1D, mientras que cada fila y columna ya está ordenada en la cuadrícula 2D?
El primer elemento en la lista en este caso tiene que ser la esquina superior izquierda ((0,0), por definición del problema). Después de esto, debe ser el elemento (1,0) o (0,1), ya que todos los demás serán más grandes que estos por definición.
Puede generalizar diciendo que el siguiente elemento más pequeño en la cuadrícula siempre está directamente debajo de un elemento ya utilizado (o el borde de la cuadrícula), y también a la derecha de un elemento ya utilizado (o el borde de la cuadrícula), ya que ambos son definido para ser más pequeño que él. Por lo tanto, en cada iteración solo debe considerar el valor más pequeño que cumpla con este requisito.
Puede mantener a los posibles candidatos en orden ordenado a medida que los encuentre (nunca más de dos estarán disponibles en una iteración), y en cada iteración verifique los nuevos valores disponibles (si los hay). Si son más bajos que el más bajo de los candidatos anteriores, agréguelos a la lista de inmediato y repita; de lo contrario, agregue el candidato anterior más bajo y compárelo con el siguiente más bajo, etc.
Desafortunadamente, no pretendo poder proporcionar una complejidad exacta de esto, ni afirmo que es lo más eficiente posible, ciertamente parece mejor que un enfoque ingenuo, y espero haberlo explicado lo suficientemente bien como para que lo entiendas.
EDITAR: Para las cuadrículas nd como esta, creo que se aplica el mismo principio básico, pero cada iteración pone a disposición n nuevos candidatos, y estos candidatos deben ser los elementos no utilizados más pequeños en cada una de las n dimensiones en este punto.
fuente