algorithm - metodo - ordenar numeros ascendente y descendente en matlab
¿Cómo ordenar la matriz amxn que tiene todas sus m filas ordenadas y n columnas ordenadas? (3)
Dada una matriz con m filas yn columnas, cada una de las cuales está ordenada. ¿Cómo ordenar eficientemente toda la matriz?
Conozco una solución que se ejecuta en O (mn log (min (m, n)). Estoy buscando una solución mejor.
El enfoque que conozco básicamente toma 2 filas / cols a la vez y aplica la operación de combinación.
Aquí hay un ejemplo:
[[1,4,7,10],
[2,5,8,11],
[3,6,9,12]]
es el martix de entrada que tiene ordenadas todas las filas y columnas.
La salida esperada es:
[1,2,3,4,5,6,7,8,9,10,11,12]
Otro ejemplo:
[[1, 2, 3, 3, 4, 5, 6, 6, 7, 7],
[1, 2, 4, 6, 7, 7, 8, 8, 9,10],
[3, 3, 4, 8, 8, 9,10,11,11,12],
[3, 3, 5, 8, 8, 9,12,12,13,14]]
Al crear un árbol de búsqueda binario, podemos lograr esto en tiempo O (mn). Tome el último elemento de la primera columna (elemento 3 en el ejemplo mencionado anteriormente) y conviértalo en una raíz. Los nodos derechos serán los n elementos mayores de la última fila y el nodo izquierdo será el elemento anterior, es decir. el (m-1) th o el primer elemento de la segunda última fila. De manera similar para este elemento, los nodos correctos serán los n elementos de esa fila. Nuevamente, m-2 será el elemento izquierdo y todos los n elementos en su fila serán los elementos correctos. De manera similar, avanzando tendremos un árbol de búsqueda binario creado en tiempo O (mn). Esto es O (mn) porque no estamos buscando mientras se está insertando, es un inserto simple mientras se desplaza desplazando el puntero del nodo raíz. Luego se realizará el recorrido de este BST, que también será O (mn).
No creo que puedas hacerlo más rápido que Ω ( mn log (min ( m , n )), al menos no en el caso general.
Supongamos (sin pérdida de generalidad) que m < n . Entonces tu matriz se ve así:
Cada círculo es una entrada de matriz y cada flecha indica una relación de orden conocida (la entrada en el origen de la flecha es más pequeña que la entrada en el destino de la flecha).
Para ordenar la matriz, debemos resolver todas las relaciones de orden desconocido, algunas de las cuales se muestran en los cuadros grises aquí:
La clasificación de todas estas cajas toma:
2 Σ k < m Ω ( k log k ) + ( n - m + 1) Ω ( m log m )
= 2 Ω ( m ² log m ) + ( n - m + 1) Ω ( m log m )
= Ω ( mn log m )
Si los elementos son enteros dentro de un cierto rango k donde K = o (mn), podemos usar la ordenación por conteo con espacio adicional para lograr O (mn), de lo contrario, el mnlog (min (m, n)) es lo mejor que podemos hacer.