Estructura De Datos

INSTRUCCIONES: Utilizando la plantilla establecida por IACC para la entrega de controles de la semana, descargable desde la plataforma del curso junto con estas instrucciones, responda las siguientes preguntas:

1) Defina en sus propios términos los siguientes conceptos:

a. Algoritmos de Búsqueda; Un algoritmo de búsqueda es un algoritmo que acepta un argumento a y trata de encontrar un registro cuya llave sea a. El algoritmo puede dar como resultado el registro entero o, lo que es más común, un apuntador dicho registró.

Podemos decir que es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

b. Algoritmos de Ordenación:

Es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida.

2) Con sus propias palabras, indique en qué consisten los siguientes procesos:

a. Inserción de datos; Requiere desplazar hacia delante (n – r) elementos. En el caso peor (r = 0) el costo en tiempo es de O(n).

b. Eliminación de datos; Requiere desplazar hacia atrás (n – r – 1) elementos. En el caso peor (r = 0) el costo en tiempo es de O(n). Para poder realizar inserciones y eliminaciones en ambos extremos con costo en tiempo de O (1), puede utilizarse un arreglo circular.

3) Explique brevemente y según sus propias palabras, los siguientes métodos de ordenación:

a. Selección: El ordenamiento por selección, al igual que el algoritmo de inserción es muy trivial, puesto que recorre el vector o la lista, buscando el elemento más pequeño y colocándolo en la posición 0 del vector, y así sucesivamente n-1 veces, tanto de grande como sea el vector. Al igual que los algoritmos anteriores, requiere O (n²).

b. Burbuja: El ordenamiento por burbuja es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. Es un algoritmo estable. El inconveniente es que es muy lento.

c. Inserción Binaria: Es una mejora del método de inserción directa. La mejora consiste en realizar una búsqueda binaria en lugar de una búsqueda secuencial, para insertar un elemento en la parte izquierda del arreglo, que ya se encuentra ordenado.

El proceso al igual que el de Inserción Directa, se repite desde el 2do hasta el n-ésimo elemento.

La búsqueda binaria consiste en dividir el arreglo por su elemento medio en dos arreglos más pequeños, y comparar el elemento con el elemento del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, el elemento se encuentra a la izquierda si no el elemento se encuentra a la derecha.

d. QuickSort: El ordenamiento rápido; es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

...