Algoritmos De Ordenamiento Externo
Enviado por cuasi9778 • 28 de Septiembre de 2012 • 1.412 Palabras (6 Páginas) • 674 Visitas
Algoritmos de ordenamiento externo
¿Qué es el algoritmo de ordenamiento externo?
Es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso.
Características de la búsqueda secuencial
La búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
Características:
1- La búsqueda se puede realizar en arreglos desordenados.
2- El método es totalmente confiable.
3- El número de comparaciones es significativa si el arreglo es muy grande.
4- En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo.
5- Cantidad mínima de comparaciones es 1.
6- Cantidad media de comparaciones es (1+N)/2.
7- Cantidad máxima de comparaciones es N.
¿Qué es ordenamiento?
Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.
Define la clasificación de los algoritmos de ordenamiento:
Existen dos tipos de algoritmos de ordenamientos los cuales son algoritmo de ordenamiento interno y externo.
Los internos:
Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo.
Los externos:
Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición donde fue colocado.
¿Qué es el método de inserción?
En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es insertado en la posición apropiada con respecto al resto de los elementos ya ordenados.
Entre estos algoritmos se encuentran el de inserción directa, Shell sort, inserción binaria y hashing.
¿Qué es el análisis de algoritmos?
El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
Insertar Cola
public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {
class Celda {
Object elemento;
int prioridad;
Celda sig;
}
private Celda cola;
public ColaPrioridad() {
cola = new Celda();
cola.sig = null;
}
public boolean vacia() {
return (cola.sig==null);
}
public Object primero() .throws ColaVaciaException {
if (vacia()) throw new ColaVaciaException();
return cola.sig.elemento;
}
public int primero_prioridad() throws ColaVaciaException {
if (vacia()) throw new ColaVaciaException();
return cola.sig.prioridad;
}
public void inserta(Object elemento, int prioridad) {
Celda p,q;
...