La ordenación o clasificación de datos (sort en inglés) es una operación consistente en disponer un conjunto (estructura) de datos en algún determinado orden con respecto a uno de los campos de los elementos del conjunto.
Ordenación
Los métodos (algoritmos) de ordenación son numerosos por lo que se suelen dividir en dos grandes grupos:
- Directos burbuja, selección, inserción.
- Indirectos (avanzados) shell, ordenación rápida, ordenación por mezcla, radixsort.
Bubblesort
El ordenamiento de burbuja compara cada elemento con todos los demás, y hace un intercambio cada vez que la prueba de comparación pasa (si están en el orden equivocado). Para ordenar de manera ascendente, cada elemento de índice I se verifica para ver si el
valor es mayor que el elemento I+1, hasta llegar al último elemento.El ordenamiento descendente hace comparaciones para ver si el I-ésimo elemento es menor que el elemento i+1.
Inserción
Este método de ordenación es similar al proceso típico de ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético, que consiste en insertar un nombre en su posición correcta dentro de una lista que ya está ordenada.
Quicksort
El algoritmo divide los n elementos de la lista a ordenar en dos partes o particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote, y una partición derecha. La partición se hace de tal forma que todos los elementos de la primera sublista (partición izquierda) son menores que todos los elementos de la segunda sublista (partición derecha). Las dos sublistas se ordenan entonces independientemente.Una vez que el pivote ha sido elegido, se utiliza para ordenar el resto de la lista en dos sublistas: una tiene todas las claves menores que el pivote y la otra todas las claves mayores o iguales que el pivote. Estas dos listas parciales se ordenan recursivamente utilizando el mismo algoritmo; es decir, se llama sucesivamente al propio algoritmo quicksort
Bin sort
Este método, también denominado clasificación por urnas, se propone conseguir funciones tiempo de ejecución de complejidad menor que O(n log n) para ordenar una lista de n elementos, siempre que se conozca alguna relación del campo clave de los elementos
respecto de las urnas.
Búsquedas
Búsqueda lineal
La búsqueda lineal o secuencial es la técnica más simple para buscar un elemento en un array (vector). Consiste el método en el recorrido de todo el vector, desde el primer elemento hasta el último, y de uno en uno. Si el vector contiene el elemento, el proceso
devolverá la posición del elemento buscado dentro del vector y, en caso contrario, un mensaje que indique la falta de éxito en la búsqueda.
Búsqueda Binaria
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la porción de la lista que podría contener al elemento. Para saber si una clave se encuentra en dicha lista, si la
clave es menor, entonces el posible registro buscado se encuentra en la primera mitad de la lista, y si es mayor, en la segunda mitad de la lista. El proceso se debe repetir hasta que se encuentre la clave, o hasta que solo quede un registro cuya clave es distinta a la buscada,
lo que significa que la búsqueda no fue exitosa.
Interpolación lineal
En general, en la interpolación lineal se utilizan dos puntos, (xa,ya) y (xb,yb), para obtener un tercer punto interpolado (x,y) a partir de la siguiente fórmula:
Bibliografía
Aguilar, L. J., Martínez, I. Z., coaut, Z. M. I., Sánchez, A. V., & Vieyra, G. Q. (1998a). Estructura de datos . New York, Estados Unidos: McGraw-Hill Education.
Joyanes, L., Zahonero, I. (2007). Estructura de datos en C++ . Madrid, España: McGraw-Hill Education.
Deitel, P., & Deitel, H. (2012). Cómo programar en Java (9th ed.). Naucalpan de Juárez, México: Pearson Educación.
Ziviani, N., & Adiego, J. (2007). Diseño de algoritmos con implementaciones en Pascal y C . Madrid, España: Paraninfo.