Programación

Algoritmos de Búsqueda Esta operación consiste en localizar el o los registros del fichero que cumplan cierta condición. La búsqueda se suele realizar de forma que uno o varios campos del registro contengan unos valores predeterminados. Denominaremos al campo o campos por los que se realiza la búsqueda clave de búsqueda. Si la búsqueda tiene éxito, se recupera el registro que cumple el criterio de búsqueda (o todos los registros que lo cumplan); si fracasa, se debe informar al usuario o al módulo que solicitó la operación de búsqueda. Para hacer la descripción más general, consideraremos búsquedas que se realizan por un solo campo, pudiendo adaptarse fácilmente los algoritmos propuestos para hacer búsquedas por varios campos. Consideraremos ficheros formados por registros de tipo REGISTRO, que incluyen al menos un campo, que denominaremos CLAVE, y que se toma como clave de búsqueda. REGISTRO es registro compuesto por CLAVE de tipo T ** otr...

Este método se basa en la técnica "divide y vencerás". Los pasos que aplica son los siguientes: Se divide el vector en dos mitades. Se ordena cada una de las dos mitades aplicando MergeSort. Se mezclan ambas mitades, obteniendo un vector ordenado. La operación de división se aplica, recursivamente, a cada una de las dos mitades obtenidas en cada paso. Cuando la partición obtenida tenga un solo elemento se la considera ordenada. A continuación se mezclarán las particiones de un elemento, obteniendo particiones ordenadas de dos elementos. El proceso de mezcla continuará, obteniendose particiones ordenadas cada vez más grandes, hasta obtener todo el vector ordenado. La operación de mezcla de dos vectores ordenados genera un nuevo vector que contiene los elementos de ambos y que conserva el orden. En este caso los dos vectores que se pretenden mezclar son realmente dos intervalos de posiciones del vector que estamos intentando ordenar. El primer subvector será el que ...

Este método aplica la técnica "divide y vencerás", subdividiendo el vector en vectores más pequeños y ordenando éstos. Para hacer esta división, se toma un valor cualquiera del vector, que se suele denominar pivote, y se realiza el desplazamiento de todos los elementos menores que él a la izquierda de éste. De la misma forma, los elementos mayores que él se desplazarán a su derecha. Con esto se garantiza que los elementos colocados a la izquierda del pivote son menores o iguales que éste, mientras los situados a su derecha serán mayores o iguales a él. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el vector. El procedimiento se repite de forma recursiva hasta que al final todas las particiones son de tamaño 1, con lo que el vector queda ordenado. Por tanto, dado un vector V de N elementos, el método de ordenación aplicará los siguientes pasos básicos: Se elige un elemento como pivote. Si el tamaño del vector es 1, está...

Este método, también conocido como método de ordenación por inserción con incrementos decrecientes, es una mejora del método de inserción directa. Consiste en ordenar por inserción los elementos que difieren S1 posiciones. A continuación se ordenan los que difieren S2 posiciones, siendo S2 Las operaciones del algoritmo se podrían esquematizar como sigue: Tomar una distancia de comparación inicial. Ordenar entre sí los elementos situados a esa distancia. Reducir la distancia de comparación. Si es mayor o igual que 1, volver al paso 2. Se pueden elegir diferentes secuencias de incrementos o distancias. En nuestro caso la distancia inicial es igual a la mitad del número de elementos del vector. En cada nueva iteración se reduce la distancia previa a la mitad, tomando en la última iteración distancia 1. PSEUDOCÓDIGO MÓDULO ordenacion_shell DATOS PARÁMETROS Transforma V() de tipo T Recibe N entera VARIABLES I, J, DIS...

Este método, también conocido como método de ordenación por vibración, es una mejora del método de la burbuja, que mezcla sus dos versiones alternativamente, realizando una pasada de izquierda a derecha y a continuación otra de derecha a izquierda, recortándose los elementos a tratar por ambos extremos del vector. Igual que en el caso de la burbuja, se puede aumentar la efectividad del método de la sacudida deteniendo la ordenación si se comprueba que en una pasada, tanto de izquierda a derecha como de derecha a izquierda, todos los elementos están ordenados. (Ver algoritmo de ordenación por sacudida con test ). El método de la sacudida se puede modificar para descartar más posiciones en los extremos, en lugar de una sola, como ocurre en los algoritmos anteriores. Si al realizar una pasada de derecha a izquierda el último intercambio afecta a las posiciones X y X+1, significa que los valores comprendidos entre las posiciones 1 y X ya están ordenados, por lo que no será necesario...

Este método también se conoce como método de la burbuja. Tiene dos versiones basadas en la misma idea: recorrer sucesivamente el vector comparando los elementos consecutivos e intercambiándolos cuando estén descolocados. En una de las versiones el vector se recorre de izquierda a derecha, desplazando los valores mayores hacia su derecha, y en la otra se recorre de derecha a izquierda, desplazando los valores menores hacia su izquierda, ambos para la clasificación en orden ascendente. Cada pasada sobre el vector lleva un nuevo elemento a su posición definitiva, y en orden, en el extremo de la zona de comparación considerada (extremo derecho en el caso de recorrido de izquierda a derecha y en el extremo izquierdo en el caso de recorrido de derecha a izquierda), por lo que en la siguiente pasada se excluye de las comparaciones. El algoritmo consiste en aplicar los siguientes pasos, considerando inicialmente todas las posiciones del vector: Se comparan los valores de las posicione...

Este método realiza sucesivas búsquedas del menor de los elementos que quedan por ordenar, colocándolo en su posición definitiva dentro de la parte del vector ordenado. Tras cada iteración I del algoritmo, los elementos situados a la izquierda del I-ésimo están ordenados. Por tanto y para cada iteración I del algoritmo (de un total de N-1) los pasos a dar son: Se selecciona la componente de menor valor, de entre las existentes entre la I-ésima posición y la última. Se intercambia el valor seleccionado con el almacenado en la posición I. PSEUDOCÓDIGO MÓDULO ordenacion_seleccion_directa DATOS PARÁMETROS Transforma V() de tipo T Recibe N entera VARIABLES I, J, K enteras AUX de tipo T INICIO Para I desde 1 hasta N-1 K ← I AUX ← V(I) Para J desde I+1 hasta N Si ( V(J) FIN CÓDIGO C /*Ordena un vector (de menor a mayor) p...