Secuenciales coordinados

La operaciones secuenciales coordinadas implica el procesamiento coordinado de dos o más listas
secuenciales para producir una única lista de salida.
Dichas lista se pueden producir ya sea por: Correspondencia (intersección) Intercalación (unión)

Correspondencia
Las listas deben de estar en orden ascendente.
1. Se inicia con la lectura del nombre inicial del la lista 1 y lo compara con el nombre inicial de la lista
2. Si encuentra una correspondencia se inserta el elemento en un nuevo archivo.

Intercalación
Es la unión de los elementos de dos listas.
La diferencia entre la correspondencia y la intercalación es que con la intercalación debe leerse totalmente cada una de ellas.

.

Ordenamiento Shell

El método de Shell es una versión mejorada del método de inserción directa recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.

CARACTERÍSTICAS

• Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal) podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.

• Se basa en comparaciones e intercambios.
• Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
• No es estable: dados dos elementos que al compararlos sean "iguales" no mantienen necesariamente el orden relativo inicial entre ellos
• El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
• Sin embargo, optimizaciones posteriores han logrado reducir esa cota... Por ejemplo, con la optimización de Robert Sedgewick se llega a O(n4/3), y con la propuesta por Vaughan Pratt se llega al orden de O(n log2n).
• En 1992, Greg Plaxton, Bjorn Poonen y Torsten Suel prueban que es posible incluso rebajar aún más esas cotas.
• En cierto modo, puede considerarse una ampliación del algortimo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
• No es un algoritmo en-línea.

EFICIENCIA

El análisis de eficiencia es un problema complicado y aun no resuelto.

Nadie ha sido capaz de establecer la mejor secuencia de incrementos cuando N es muy grande.
Una medida de eficiencia es:
Contar el # de comparaciones (C)
Contar el # de movimientos de items (M)
Estos están en función de el #(n) de items a ser ordenados.
Un "buen algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.
La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2

Archivos Secuenciales

Archivo secuencial es la forma más simple de almacenar y recuperar registros en un archivo.
En un archivo secuencial, se almacenan los registros uno tras otro. El primer registro almacenado se coloca al principio del archivo y el segundo se almacena inmediatamente después.

Operaciones

Las operaciones que podemos realizar sobre éstos archivos son:

....Creación
La creación exige organización, estructura, localización o reserva de espacio en el soporte
de almacenamiento, transferencia del archivo del soporte antiguo al nuevo.
Es la operación que permite al usuario acceder al archivo de datos para conocer el contenido
de uno, varios o todos los registros

....Actualización
Es la operación que permite tener actualizado (puesto al día) el archivo, de tal modo que sea posible realizar las siguientes operaciones con sus registros: Consulta del contenido de un registro. Inserción de un registro nuevo en el archivo.

....Clasificación
Reubicación de los registros de tal forma que queden ordenados según determinados criterios.
Una operación muy importante en un archivo es la clasificación u ordenación. Esta clasificación
se realizará de acuerdo con el valor de un campo específico, pudiendo ser ascendente (creciente) o descendente (decreciente): alfabética o numérica.

....Borrado
Es la operación inversa a la creación de un archivo. Cuando se destruye (anula o borra) un archivo, éste ya no se puede utilizar y, por consiguiente, no se podrá acceder a ninguno de sus registros.

...Reorganización De Un Archivo
La reorganización suele consistir en la copia de un nuevo archivo a partir del archivo modificado, a fin de obtener una nueva estructura lo más óptima posible.

.

Indizacion de Archivos

Es la aplicación de incluir índices en el almacenamiento de los archivos;
de esta forma nos será más fácil buscar algún registro sin necesidad de ver todo el archivo.
Un índice en un archivo consiste en un listado de los valores del campo clave que ocurren en el archivo,
junto con la posición de registro correspondiente en el almacenamiento masivo.

• La colocación de un listado al inicio del archivo: para la identificación del contenido.
• La presentación de un segundo índice: para reflejar la información de cada punto principal del índice anterior.
• La actualización de los índices: Cuando se insertan y eliminan archivos, es preciso actualizar los
• índices para evitar contratiempos actualizando un archivo.
• La organización de un índice: Nos evita examinar archivo por archivo para recuperar
• algún registro buscado; por lo tanto ahorraríamos tiempo si tenemos una adecuado organización de los índices.

Longitud de Registros

Registros de Longitud Fija: (Constantes) Conjunto de campos cuya extencion no varia a la utilizacion del programa. Fijados desde el inicio, reservando el espacio necesario, sin posibilidad de salir de ese espacio.

Registros de Longitud Variable: (Variable) Conjunto de campos cuya extencion varia mientras el programa es ejecutado. Cada byte o caracter es un registro el cual se va almasenando.

.

Archivos y su clasificasión

.

En la materia de estructura de archivos, como su nombre lo dice, vemos la manera general en que los archivos se organizan, se componen, se manipulan, etc. los archivos en si; es por eso que como primer paso definiremos lo que es un archivo.



Archivo:
Colección de registros del mismo tipo, lógicamente ordenados, organizados y relacionados, almacenados dentro de alguna parte de la computadora o memoria secundaria, y que pueden ser manipulados. La organización, acceso y manipulación de estos, depende de la estructura de archivos aplicada.
Los archivos tienen dependencia de la información respecto a los programas, quienes solo pueden acceder a ellos. Su información es permanente siempre y cuando estén localizados dentro de un dispositivo de almacenamiento secundario.

Clasificasión de Archivos:
Hay varios tipos de clasificasiones, algunas de ellas son las siguientes.

...... Según su Acceso
- Secuencial: Uno tras otro.
- Directo: Directo al registro que interesa.
- Por índice: Con una dirección de acceso a él.
- Dinámico: De manera aleatoria.

...... Típos de Valores Permitidos a Cada Byte
- De textos: Con formato relacionado con el código ASCII.
- Binarios: Con 0 y 1.

...... Direccion del Flujo de Datos
- De entrada: Acepta la gravacion de nuevos datos (escritura)
- De salida: Solo lee los datos ya existentes (lectura)
- Convinados: De lectura y escritura a la vez

...... Por su Función
- Maestros: Son los que contienen los datos mas importantes y los datos almasenados en ellos son permanentes.
- De transacciones: Recolecta los cambios hechos en el archivo maestro.
- De reporte: El que ayuda a la realizacion de busquedas. Se genera un archivo de reporte despues de cada búsqueda o consulta realizada.
- Programa: Los ejecutables que contienen las instrucciones de la estructura de los programas que corremos en la computadora.
- De texto: Formato para almasenar estructuras de datos en forma de archivos (datos alfanuméricos).