Metodos de ordenamiento (estructura de datos)

Solo disponible en BuenasTareas
  • Páginas : 5 (1239 palabras )
  • Descarga(s) : 0
  • Publicado : 10 de diciembre de 2011
Leer documento completo
Vista previa del texto
HASHING POR PLIEGUE
En esta técnica se busca el valor de la llave que es dividido en partes, cada una en las cuales (excepto la última) tiene el mismo número de dígitos que tiene la dirección relativa objetivo.
Las particiones después son plegadas una sobre la otra y sumadas. El resultado con el dígito de mayor orden truncado, si es necesario, será la dirección relativa.
EJEMPLO
Considere elvalor de llave 123456789 y suponga que la dirección relativa objetiva tendrá 4 dígitos, el valor de la llave es particionado de derecha a izquierda en partes de 4 dígitos.

1 2345 6789Partición 1 Partición 2 Partición 3
Después se intercambian de derecha a izquierda los números de la primera y y nos da la tercera partición.

1 2345 9876Partición 1 Partición 2 Partición 3
Después de sumar el valor de cada partición.
1+2345+9876=13221
Eliminando el digito de mayor cifra queda así.
3221 Esta será la dirección relativa.

HASHING POR RESIDUO DE LA DIVISIÓN
En estemétodo se divide el valor de la llave entre un numero apropiado, y después utilizamos el residuo de la división como dirección relativa para el registro
Mientras que el valor calculado de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor correcto no puede ser tan facil. Se deven tomar varios factores para seleccionar el divisor:
El rango devalores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño del espacio de direcciones relativas. Si se sabe que el archivo va a contener por lo menos n registros, entonces tendremos que hacer que divisor > n, suponiendo que solamente un registro puede ser almacenado en una dirección relativa dada.
El divisor deberáseleccionarse de tal forma que la probabilidad de colisión sea minimizada. ¿Cómo escoger este número? Mediante investigaciones se ha demostrado que los divisores que son números pares tienden a comportase pobremente, especialmente con los conjuntos de valores de llave que son predominantemente impares.
Algunas investigaciones sugieren que el divisor deberá ser un número primo. Sin embargo, otras sugierenque los divisores no primos trabajan también como los divisores primos, siempre y cuando los divisores no primos no contengan ningún factor primo menor de 20. Lo más común es elegir el número primo más próximo al total de direcciones
EJEMPLO
Independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo está completamente lleno, la probabilidad de colisióncrece dramáticamente. La saturación de archivo se mide mediante su factor de carga, el cual se define como la relación del número de registros en el archivo contra el número de registros que el archivo podría contener si estuviese completamente lleno.
Todas las funciones hash comienzan a trabajar probablemente cuando el archivo esta casi lleno. Por lo general el máximo factor de carga que puedetolerarse en un archivo para un rendimiento razonable es de entre el 70 % y 80%.
BUSQUEDA BINARIA EN JAVA.

Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de interacciones necesarias.

Esta muy recomendado para buscar en arrays de gran tamaño. Por ejemplo, en un contenido 50.000.000 elementos, para implementar este algoritmo se...
tracking img