Ordenación de datos y algoritmos

Ordenar

Ordenar significa reorganizar un conjunto de datos u objetos en una secuencia definida. Se clasifican en 2 categorías:

Ordenación Interna

Se utiliza cuando los elementos del arreglo se encuentran en la memoria principal de la computadora.

Ordenación Externa

Se utiliza cuando los elementos se encuentran en archivos almacenados en dispositivos de almacenamiento secundario como discos, cintas, etc.

Tipo de ordenación interna

Los métodos de ordenación interna pueden ser clasificados en dos tipos: Directos e indirectos.

Métodos directos (n^2)

Como inserción, selección directa, burbuja, shell.

Métodos logarítmicos (N*logN, logN)

Como quicksort, heapsort y montículo, etc.

Primero, conceptos

Algoritmo: Conjunto de reglas para resolver un problema. Su ejecución requiere de diversos recursos.

Eficiencia: Cantidad de recursos de cómputo que necesita.

Recursos que se necesitan

Recursos consumidos. Ejemplo: ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo?

Factores que influyen en el consumo de recursos

Factores externos, la máquina donde se ejecute, el lenguaje de programación y el compilador usado, la implementación que haga el programador del algoritmo, tamaño de los datos de entrada, contenido de los datos de entrada.

Complejidad de los algoritmos

Tiempos y espacio de complejidad se analizan con la notación asintótica.

Notación Asintótica

Describe el comportamiento de la complejidad del tiempo y espacio que un algoritmo necesita.

La gran O

La notación de la O provee de los límites superiores de la función f.

Inserción y selección directa

//a es un arreglo de n elementos

Método de Shell

Este método es una versión mejorada del método inserción directa, se llama así en honor a su autor, Donald L. Shell.

Método Quicksort

Actualmente es el más eficiente y veloz.

Búsqueda Binaria

Esta búsqueda consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el central. En caso de no ser iguales se redefinen los extremos del intervalo.

Búsqueda por transformación de claves o Hash

Permite tener acceso directamente a los datos. Se utilizan funciones Hash para calcular el índice en el cual vamos a almacenar el dato y posteriormente buscarlo.

Funciones Hash

Es importante seleccionar una buena función hash, a continuación se presentan algunas.

Solución de Colisiones

Una colisión ocurre cuando se generan dos índices iguales con diferentes claves. Los métodos para solucionar colisiones se clasifican en Reasignación, Arreglos Anidados, Encadenamiento.