Matriz ordenada

Una matriz ordenada es una estructura de datos de matriz en la que cada elemento se ordena numéricamente, alfabéticamente o en otro orden, y se coloca en direcciones espaciadas de manera uniforme en la memoria de la computadora. Se utiliza generalmente en informática para implementar tablas de búsqueda estáticas que contengan múltiples valores que tengan el mismo tipo de datos . Ordenar una matriz es útil para organizar datos en forma ordenada y recuperarlos rápidamente.

Las matrices ordenadas son la estructura de datos que más espacio ahorra y con la mejor localidad de referencia para los datos almacenados secuencialmente. ^{[ cita requerida ]}

Los elementos dentro de una matriz ordenada se encuentran mediante una búsqueda binaria , en O(log n ); por lo tanto, las matrices ordenadas son adecuadas para los casos en los que se necesita poder buscar elementos rápidamente, por ejemplo, como una estructura de datos de conjunto o multiconjunto . Esta complejidad para las búsquedas es la misma que para los árboles de búsqueda binaria autoequilibrados .

En algunas estructuras de datos se utiliza una matriz de estructuras. En tales casos, se pueden utilizar los mismos métodos de ordenación para ordenar las estructuras según alguna clave como elemento de estructura; por ejemplo, ordenar registros de estudiantes según números de matrícula, nombres o calificaciones.

Si se utiliza una matriz dinámica ordenada , es posible insertar y eliminar elementos. La inserción y eliminación de elementos en una matriz ordenada se ejecuta en O( n ), debido a la necesidad de desplazar todos los elementos que siguen al elemento que se va a insertar o eliminar; en comparación, un árbol binario de búsqueda autoequilibrado inserta y elimina en O(log n ). En el caso en que los elementos se eliminen o inserten al final, una matriz dinámica ordenada puede hacer esto en tiempo amortizado O(1), mientras que un árbol binario de búsqueda autoequilibrado siempre opera en O(log n ).

Los elementos de una matriz ordenada se pueden buscar por su índice ( acceso aleatorio ) en el tiempo O(1), una operación que toma un tiempo O(log n ) u O( n ) para estructuras de datos más complejas.

John von Neumann escribió el primer programa de ordenamiento de matrices ( merge sort ) en 1945, cuando todavía se estaba construyendo la primera computadora con programa almacenado . ^{[1] [2]}

• Algoritmo de ordenación
• Algoritmo de búsqueda binaria
• Montón (estructura de datos)
• Estructura de datos de búsqueda