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 rdiccionarios, 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.

5.1.1 Fundamento Algoritmos 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. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

5.1.2 Ejemplos Algoritmos Ordenamiento

→ Internos

• Inserción directa.
• Inserción binaria.
• 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.

5.1.2.1 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.
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 Ordenamiento 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 Ordenamiento 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 Ordenamiento 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.1.2.5 Ordenamiento Por Combinación

También llamado algoritmo de Ordenamiento por mezcla (Merge sort en inglés) es un algoritmo de ordenación externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).

5.2 Métodos de búsqueda

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.

5.2.1 Fundamento de Algoritmos de Búsqueda

La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades: - Determinar si el elemento buscado se encuentra en el conjunto en el que se busca. - Si el elemento está en el conjunto, hallar la posición en la que se encuentra. En este apartado nos centramos en la búsqueda interna. Como principales algoritmos de búsqueda tenemos la búsqueda secuencial, la binaria y la búsqueda utilizando tablas de hash.

5.2.1.1 Búsqueda 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 Búsqueda 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.

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

♥ Aritmetica Molecular

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 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 de conversión se define como: h(x) =c donde c se obtiene eliminado dígitos a ambos extremos de x2. Se deben utilizar las mismas posiciones de x2 para todas las claves.