Friday, May 21, 2010

Metodos Ordenamiento y busqueda

Presentado por:
-Andres Fernando Leon codigo: 624503
-Lizzar Alfredo rivas codigo:624688
-Julian Alexander Peña Bayona codigo: 624653

Mapa conceptual metodos Ordenamiento


Metodos Ordenamiento
¿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.

Ej. de ordenamientos:

Dir. telefónico, tablas de contenido, bibliotecas y diccionarios, etc.

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.

Cuándo conviene usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Tipos de ordenamientos:

Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
  • 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 (a[1], a[500], etc).

  • Los externos: Son aquellos en los que los valoresa 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 accesada (posición 1, posición 500, etc).


Eficiencia en tiempo de ejecución:

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

Algoritmos de ordenamiento:

Internos:

1. Inserción directa.

2. Inserción binaria.

3. Inserción directa.

1. Selección directa.

2. Selección directa.

1. Burbuja.

4. Intercambio directo.

1. Shell.

5. Inserción disminución incremental.

1. Heap.

2. Tournament.

6. Ordenamiento de árbol.

1. Quick sort.

Clasificación de los algoritmos de ordenamiento de información:

El hecho de que la información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial.

A continuación se describirán 4 grupos de algoritmos para ordenar información:

Algoritmos 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 INSERCION DIRECTA, SHELL SORT, INSERCION BINARIA y HASHING.

Algoritmos de intercambio:

En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios.

Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT.

Algoritmos de selección:

En este tipo de algoritmos se SELECCIONA o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este proceso se repite para el resto de los elementos hasta que todos son analizados.
Entre estos algoritmos se encuentra el de SELECCION DIRECTA.

Algoritmos de 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.

Los métodossimples son: Inserción (o por inserción directa), selección, burbuja y shell, en dónde el último es una extensión al método de inserción, siendo más rápido. Los métodos más complejos son el quick-sort (ordenación rápida) y el heap sort.

A continuación se mostrarán los métodos de ordenamiento más simples.

METODO DE INSERCIÓN.


Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).

Procedimiento Insertion Sort

Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[].

paso 1: [Para cada pos. del arreglo] For i <- 2 to N do

paso 2: [Inicializa v y j] v <- a[i]

j <- i.

paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do

paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1],

paso 5: [Decrementa j] set j <- j-1.

paso 5: [Inserta v en su posición] Set a[j] <- v.

paso 6: [Fin] End.

Ejemplo:

Si el arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'], el algoritmo va a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's' y lo asigna a v y itoma el valor de la posición actual de v.

Luego compara esta 's' con lo que hay en la posición j-1, es decir, con 'a'. Debido a que 's' no es menor que 'a' no sucede nada y avanza i.

Ahora v toma el valor 'o' y lo compara con 's', como es menor recorre a la 's' a la posición de la 'o'; decrementa j, la cual ahora tiene la posición en dónde estaba la 's'; compara a 'o' con a[j-1] , es decir, con 'a'. Como no es menor que la 'a' sale del for y pone la 'o' en la posición a[j]. El resultado hasta este punto es el arreglo siguiente: a = ['a','o','s','r',....]

Así se continúa y el resultado final es el arreglo ordenado :

a = ['a','a','e','e','g','i','l','m','n','o','p','r','s','t','x']

MÉTODO DE SELECCIÓN.


El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.

Procedimiento Selection Sort

paso 1: [Para cada pos. del arreglo] For i <- 1 to N do

paso 2: [Inicializa la pos. del menor] menor <- i

paso 3: [Recorre todo el arreglo] For j <- i+1 to N do

paso 4: [Si a[j] es menor] If a[j] <>

paso 5: [Reasigna el apuntador al menor] min = j

paso 6: [Intercambia los datos de la pos.

min y posición i] Swap(a, min, j).

paso 7: [Fin] End.

Ejemplo:

El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].

Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'.

Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].

El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'.

El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].

De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.

El número de comparaciones que realiza este algoritmo es :

Para el primer elemento se comparan n-1 datos, en general para el elemento i-ésimo se hacen n-i comparaciones, por lo tanto, el total de comparaciones es:
la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).

MÉTODO BURBUJA.


El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar.

Procedimiento Bubble Sort

paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do

paso 2: [Inicia desde la segunda pos.] For j <- 2 to i do
paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] <>
paso 5: [Los intercambia] Swap(a, j-1, j).
paso 6: [Fin] End.
Tiempo de ejecución del algoritmo burbuja:
1. Para el mejor caso (un paso) O(n)
2. Peor caso n(n-1)/2
3. Promedio O(n2)

Implementacion en java Bubble sort:

public class BubleSort {
public static void main(String args[]){
int arrayEntrada[]={321, 123, 213, 234, 1, 4, 5, 6}; //Este es el array de elementos que vamos a ordenar

bubleSort(arrayEntrada); //llamada al metodo bubleSort
//tambien podriamos escribir PruebaBubleSort.bubleSort por ser metodo static
//Esta llamada modifica el contenido de arrayEntrada
for (int i=0;i < sorted =" false;" i="0;" sorted="true;" j="a.length-1;">i; j--){
if(a[j]

MÉTODO DE SHELLSORT.

Ordenamiento de disminución incremental.
Nombrado así debido a su inventor Donald Shell.
Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.


Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.

Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.


El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.


Shell sort en java:

public class ShellSort {

public static void main(String args[]){
int arrayEntrada[]={321, 123, 213, 234, 1, 4, 5, 6}; //Este es el array de elementos que vamos a ordenar

shellSort(arrayEntrada); //llamada al metodo shellSort
for (int i=0;i < gap =" a.length"> 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) ){
for( int i = gap; i < tmp =" a[" j =" i;">= gap && tmp <>


Procedimiento Shell Sort;
const
MAXINC = _____;
incrementos = array[1..MAXINC] of integer;
var
j,p,num,incre,k:integer;

begin
for incre := 1 to MAXINC do begin /* para cada uno de los incrementos */
k := inc[incre]; /* k recibe un tipo de incremento */
for p := k+1 to MAXREG do begin /* inserción directa para el grupo que se encuentra cada K posiciones */
num := reg[p];
j := p-k;
while (j>0) AND (num <>
reg[j+k] := reg[j];
j := j - k;
end;
reg[j+k] := num;
end
end
end;


Metodo Merge en java:

public class MergeSort {

public static void main(String args[]){
int arrayEntrada[]={321, 123, 213, 234, 1, 4, 5, 6}; //Este es el array de elementos que vamos a ordenar

mergeSort(arrayEntrada); //llamada al metodo mergeSort
for (int i=0;i <>
System.out.print(arrayEntrada[i]+" ");
}//fin del for
}//fin del main

public static void mergeSort( int a[ ]){
int tmpArray[] = new int[ a.length ];

mergeSort( a, tmpArray, 0, a.length - 1 );
}
private static void mergeSort( int a[ ], int tmpArray[],int left, int right ){
if( left <>
{
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}

private static void merge( int a[ ],int tmpArray[],int leftPos, int rightPos, int rightEnd){
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;

// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd ){
if( a[ leftPos ]<( a[ rightPos ] ) ){
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
}
else{
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
}
}
while( leftPos <= leftEnd ){ // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
}
while( rightPos <= rightEnd ){ // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
}
// Copy TmpArray back
for( int i = 0; i <>
a[ rightEnd ] = tmpArray[ rightEnd ];
}
}

Mapa conceptual metodos busqueda:


Metodos Busqueda

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.
Siendo el array de una dimensión o lista una estructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: búsqueda lineal y búsqueda binaria.

Búsqueda Secuencial

La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

Codificación:

void sequential_search(int x[100], int search_num)

{

int index = 0;
while((index <>

{

// Loop while the number is not found and while more elements remain.
if(x[index] != search_num)

{ // If current element is not the one for which we are
index++; // searching, increment subscript index.

}
}
return(index);
}

Búsqueda Secuencial Indexada

Descripción de la técnica.

Un método popular para superar las desventajas de los archivos secuenciales es el del archivo secuencial indexado; pero implica un aumento en la cantidad de espacio requerida.

Funciona de la siguiente manera:

Se reserva una tabla auxiliar llamada índice además del archivo ordenado mismo. Cada elemento en el indice consta de una llave kindex y un apuntador al registro en el archivo que corresponde a kindex. Los elementos en el indice al igual que los elementos en el archivo, deben estar ordenados en la llave. Si el indice es de un octavo del tamaño del archivo, se representa en el indice cada octavo registra el archivo.

Codificación.

Algoritmo de Búsqueda Secuencial Indexada:

PROCEDURE B_S_INDEXADA (llave:integer; var pocis:integer);

Var i,n:integer;

f:boolean;

begin

f:=false;

i:=1;

while (i

f:= true;

else

inc(i);

if i=1 then

linf:=1

else

linf:=pindex[i-1];

if f then

lsup:=pindex[i]-1

else

lsup:=n;

j:=linf; f:=false;

while(j<=lsup) ands (not f) do

if k[j]="llave" then f:="true"

else

inc(j);

if f then posic:="j"

else

posic:="0;"

end;

Búsqueda Binaria

La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.

Si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina búsqueda binaria.

La búsqueda binaria utiliza un método de `divide y vencerás'para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.

En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este porceso, utilizando el elemento central de esa sublista.

Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:

· La lista debe estar ordenada en un orden específico de acuerdo al valor de la llave.

· Debe conocerse el número de registros.

Algoritmo:

· Se compara la llave buscada con la llave localizada al centro del arreglo.

· Si la llave analizada corresponde a la buscada fin de búsqueda si no.

· Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.

· El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero , lo cual implica que el valor de la llave buscada no esta en la lista.

El esfuerzo máximo para este algoritmo es de log2n. El mínimo de 1 y en promedio ½ log2 n.

Ventajas de la técnica.

La búsqueda binaria es un método eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación previa del archivo.

La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los datos estén ordenados.

Es mas rapido por su recursividad, su mayor ventaja es con los archivos extensos.

El codigo del procedimiento de esta busqueda es corto en comparacion con las demas tecnicas de busqueda.

En esencia, con una sola comparacion eliminamos la mitad de la tabla; este es el metodo mas eficiente de buscar en una lista ordenada sin emplear tablas o indices adicionales.

Desventajas de la técnica.

La búsqueda binaria tiene, sin embargo, inconvenientes a resaltar:

El archivo debe estar ordenado y el almacenamietno de un archivo ordenado suele plantear problemas en las inserciones y eliminaciones de elementos.

No revisa todos los elementos del archivo, requiere que todos los elementos esten ordenados

Esta busqueda mas de uno o dos accesos si el archivo es enorme;y mantener ese archivo ordenado es muy costoso.

Principales Aplicaciones.

Ejemplo: Árbol Binario de Búsqueda:

Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol.

Solución:

Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por una de las ramas).

La combinación de resultados es trivial: la solución del subproblema es también la del problema global.

Supongamos la lista

1231

1473

1545

1834

1892

1898 elemento central


1983

2005

2446

2685

3200

Si está buscando el elemento 1983, se examina el número central 1898 en la sexta posición. Ya que 1983 es mayor que 1898, se desprecia la primera sublista y nos centramos en la segunda

1983

2005

2446 elemento central

2685

3200

El número central de esta sublista es 2446 y el elemento buscado es 1983 menos que 2446; eliminamos la segunda sublista y nos queda

1983

2005

Como no hay término centralm elegimos el término inmediatamente anterior al término central, 1983, que es el buscado.

Se han necesitado tres comparaciones, mientras que la búsqueda secuencial hubiese necesitado siete.

Búsqueda por Hash

Definición:

Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado.

La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2)

Pero : K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.


A las técnicas de calculo de direcciones también se les conoce como:

  • Técnicas de almacenamiento disperso
  • Técnicas aleatorias

  • Métodos de transformación de llave - a- dirección

  • Técnicas de direccionamiento directo

  • Métodos de tabla Hash

  • Métodos de Hashing

Pero el término mas usado es el de hashing. Al cálculo que se realiza para obtener una dirección a partir de una llave se le conoce como función hash.

Ventajas de la técnica.

  1. Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar

  2. Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones

  3. No se requiere almacenamiento adicional para los índices.

Desventajas de la técnica.

  1. No pueden usarse registros de longitud variable
  2. El archivo no esta clasificado
  3. No permite llaves repetidas
  4. Solo permite acceso por una sola llave
Cuadro comparativo metodos ordenamiento y busqueda



Biliografia-DERECHOS DE AUTOR:

· Capítulo 21: Métodos de ordenamiento y búsqueda. De:

http://www.mailxmail.com/curso-aprende-programar/metodos-ordenamiento-busqueda

· Algoritmos de búsqueda, de:

http://html.rincondelvago.com/algoritmos-de-busqueda.html

· Binary Search Illustrating Divide and Conquer, de:

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=4

· Images, Google images, de:

Images.google.com

  • metodos ordenamiento, de:
www.wikipedia.org
  • reseña sobre metodos ordenamiento y busqueda, de:
www.monografias.com
  • Trabajos sobre metodos ordenamiento, de
www.rincondelvago.com
  • Busqueda en Google con las palabras entre comillas: "Metodos de ordenamiento y busqueda". de:
www.google.com

1 comment: