lunes, 13 de mayo de 2013

métodos de ordenamiento


Un algoritmo de ordenamiento 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.
Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:  La más común es clasificar según el lugar donde se realice la ordenación
·         Algoritmos de ordenamiento interno: en la memoria del ordenador.
·         Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:
·         Algoritmos de ordenación natural: Tarda lo mínimo posible cuando la entrada está ordenada.
·         Algoritmos de ordenación no natural: Tarda lo mínimo posible cuando la entrada está inversamente ordenada.
Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha.

Ordenación por intercambio (burbuja)

Es uno de los métodos relativamente más sencillo e intuitivo, pero también resulta ser muy ineficiente. Se basa en la ordenación por cambio, y recibe su nombre de la semejanza con las burbujas de un depósito de agua donde cada burbuja busca su propio nivel.
Los pasos a efectuar en el caso de una ordenación ascendente (en el caso de la ordenación descenderte solo habría que cambiar el signo de comparación) son:
1. Comparar el primer y segundo elemento, intercambiarlos si el primero es mayor que el segundo; luego se compara el primero con el tercero, intercambiándose en caso necesario, y el proceso se repite hasta llegar al último elemento.

2. Se repite el paso anterior, pero ahora con el segundo y tercero, en caso de ser necesario se intercambian, y así hasta llegar a comparar el segundo con el ultimo.
Consideremos el siguiente ejemplo. Se cuenta con un vector de 6 posiciones donde se inicia una lista de números { 7, 2, 8, 3, 5, 1 }, la cual será ordenada en forma ascendente { 1, 2, 3, 5, 7, 8 }, observe como se declara una variable constante entera llamada n la cual tiene un valor de 6, enseguida se declara un vector de tipo entero que contendrá una cantidad n de casillas, en este caso 6, declaramos también las variables i y j que nos ayudaran a desplazarnos entre casilla y  casilla para hacer las comparaciones. Y finalmente la variable tem, almacenara temporalmente el valor a intercambiar entre las casillas que lo necesiten.
For (int i = 0; i < n-1; i++)
For (int j = i + 1; j < n; j++) {
if ( v[i] > v[j] ) { //realiza la comparación
int tem = v[i]; //si es cierta intercambia los datos
v[i] = v[j];
v[j] = tem;
}
}

Método de selección

La idea básica es encontrar el elemento más pequeño (grande), en orden ascendente de la lista, e  intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta que el último elemento ha sido transferido a su posición correcta.
El algoritmo de ordenación depende a su vez del algoritmo necesario para localizar el componente mayor (menor) de un array. Es un proceso muy similar al método de la burbuja pero haciendo más eficiente la búsqueda y evitando intercambios innecesarios.
for (int i = 0, j = 0, k = 0; i < n-1; i++) {
k = i;
for (j = i+1; j < n; j++)
if ( v[k] > v[j] )
k = j;
int tem = v[i];
v[i] = v[k];
v[k] = tem;
}
}

Método de Inserción

Este método también se denomina “método del jugador de cartas”, por la semejanza con la forma de clasificar las cartas de una baraja, insertando cada carta en el lugar adecuado.
El algoritmo ordena los dos primeros elementos de la lista, a continuación el tercer elemento se inserta en la posición que corresponda, el cuarto se inserta en la lista de tres elementos, y así sucesivamente. Este proceso continua hasta que la lista este totalmente ordenada.
for (int i = 1, j = 0; i < n; i++) {
int tem = v[i];
j = i - 1;
while ( j >= 0 && tem < v[j]) {
v[j+1] = v[j];
j--;
}
v[j+1] = tem;
}
}
Ordenación basada en comparaciones (Heap Sort)

Es una variante del algoritmo de selección, El ordenamiento por montículos (Heap sort) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo
(heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Ordenamiento Por Enumeración

En este tipo de algoritmos cada elemento es comparado contra los demás. En la comparación se cuenta cuántos elementos son más pequeños que el elemento que se está analizando, generando así una ENUMERACION. El número generado para cada elemento indicará su posición.
No basado en comparación.

jueves, 2 de mayo de 2013

estructura de archivos directos

unidad 4


ESTRUCTURA DE ARCHIVOS DIRECTOS

Son aquellos en los que los registros se pueden localizar mediante una dirección. El acceso a los registros es directo.

La organización directa es aquella que permite un posicionamiento sobre registros específicos al localizar una llave. Lo anterior permite agilizar la localización de un dato en un archivo determinado al no requerirse el procesamiento de los registros contiguos previos

Los archivos directos explotan la capacidad de los discos para acceder directamente a cualquier bloque de dirección conocida. Como en los archivos secuenciales y secuenciales indexados, se requiere un campo clave en cada registro. Sin embargo, aquí no hay concepto de ordenamiento secuencial.


Estructura


1.-Ajuste de llave a esqueleto: Este método se utiliza cuando la llave contiene digitos y opcionalmente caracteres alfabéticos. El algoritmo de asignación consiste en tomar de la llave aquellos caracteres (preferentemente digitos) que presenten mayor variación y utilizarlos como dirección en un esqueleto previamente creado. El esqueleto contendrá la cantidad de registros inicialmente estimados y en forma contigua al área de desborde para los sinónimos resultantes

2.-Archivo clasificado para búsqueda binaria: Se requiere que el archivo principal se mantenga ordenado respecto a la llave en todo momento. La ventaja de este método reside en la alta velocidad de acceso; su desventaja consiste en el tiempo que debe invertirse para mantener clasificado al archivo en todo momento. Este método se utiliza cuando el tiempo de búsqueda tiene una prioridad extremadamente alta en relación al tiempo de actualización.

3.-Transformación de llaves (Hashing): Este método consiste en descomponer la llave en múltiples fragmentos y mediante la aplicación de diverso algoritmos, dar origen a un numero en un intervalo determinado y utilizarlo como dirección de registro en el esqueleto.

4.-Relación directa - Llave dirección: Este método es aplicable para sistemas donde los elementos a registrar reciben un folio consecutivo como llave. La llave del registro se hace corresponder con la dirección física de este, por lo que la velocidad de acceso es extremadamente alta.


A cada archivo relativo debe definírsele una relación que será utilizada para
obtener una dirección física (o lógica) a partir de un valor llave. Esta relación H es
una función de mapeo y se obtiene mediante métodos de conversión clave dirección o técnicas hashing

técnica de Hashing

En informática , Hashing es un método para resumir o identificar un dato a través de la probabilidad , utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.



Una función de hash en funcionamiento 

Una función de hash es una función para sumarizar o identificar probabilísticamente un gran conjunto de información ( dominio ), dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjunto de partida y de llegada y en cómo afectan a la salida similaridades o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son. 

Son usadas en múltiples aplicaciones, como los arrays asociativos , criptografía , procesamiento de datos y firmas digitales entre otros. Una buena función de hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrá identificar unívocamente las entradas (ver función inyectiva ). 

Muchos sistemas relacionados con la seguridad informática usan funciones o tablas de hashing . 



Doble Hashing

Consiste en aplicar una segunda función hashing sobre la clave que provoca colisión. El espacio de dirección objetivo del segundo hash puede ser el mismo archivo relativo (direccionamiento abierto) o bien un archivo de desborde separado (separación de desborde).