5 MÉTODOS DE ORDENAMIENTO Y BÚSQUEDA.

5.1 MÉTODOS DE 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 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 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 nlong 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

5.1.1 FUNDAMENTO DE LOS ALGORITMOS DE ORDENAMIENTO.

Algoritmos de ordenamiento:

Internos:

• Inserción directa.

• Inserción directa.

• Inserción binaria.

• Selección directa.

• Selección directa.

• Intercambio directo.

• Burbuja.

• Shake.

• Inserción disminución incremental.

• Shell.

• Ordenamiento de árbol.

• Heap.

• Tournament.

• Sort particionado.

• Quick sort.

• Merge sort.

• Radix sort.

• Cálculo de dirección .

Externos:

• Straight merging.

• Natural merging.

• Balanced multiway merging.

• Polyphase sort.

• Distribution of initial runs.

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.

5.1.2 EJEMPLOS DE ALGORITMOS DE ORDENAMIENTO.

 5.1.2.1 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.

Los métodos simples 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.

  

5.1.2.2 POR 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.

5.1.2.3 POR 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.

5.1.2.4 POR 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.

5.2 MÉTODOS DE BÚSQUEDA.

5.2.1 FUNDAMENTO DE LOS ALGORITMOS DE BÚSQUEDA.

5.2.1.1 SECUENCIAL.

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

5.2.1.2 BINARIA.

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.

Esta búsqueda 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 este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sablista. Este tipo de búsqueda se utiliza en vectores ordenados.

5.2.1.3 TRANSFORMACIÓN DE CLAVES.

Existen numerosos métodos de transformación de claves. Todos ellos tienen la necesidad de convertir claves en direcciones. En escancia la función de conversión equivale a una caja negra que podríamos llamar calculador de direcciones. Cuando se desea localizar un elemento de clave X, el indicador de direcciones indicará en qué posición del array estará situado el elemento.

• Truncamiento: Ignora parte de la clave y se utiliza la parte restante directamente como índice (considerando campos no numéricos y sis códigos numéricos). Si las claves, por ejemplo; son enteros de ocho dígitos y la tabla de transformación contiene tiene mil posiciones, entonces el primero, segundo y quinto dígitos desde la derecha pueden formar la función de conversión. Ejemplo: 72588495 se convierte en 895. El truncamiento es un método muy rápido, pero falla para distribuir las claves de modo uniforme.

• Plegamiento: La técnica de plegamiento consiste en la partición de la clave en diferentes partes y la combinación de las partes en un modo conveniente (a menudo utilizando suma o multiplicación) para obtener el índice.

• Aritmética modular: Convertir la clave a un entero, dividir por el tamaño del rango del índice y tomar el resto como resultado. La función de conversión utilizada es mod (modulo de la resta o división).

• Mitad del cuadro: Este método consiste en calcular el cuadro de la clave x. La función reconversión se define como: h(x) =c

donde c se obtiene eliminado digitó a ambos extremos de x2. Se deben utilizar las mismas posiciones de x2 para todas las claves.