Metodos de ordenación y busqueda en c

Métodos de Ordenación y Búsqueda en C

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” (Gonzalo Ferreira Cortés).

CODIFICACIÓN EN C++
[pic]

2. ORDENAMIENTO POR INSERCIÓN DIRECTADESCRIPCIÓN.El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones. Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto con SelectionSort y BubbleSort.Se basa en intentar construir una lista ordenada en el interior del array a 
ordenar. De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones. Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro decomparación, tal que dados dos elementos nos diga si están en orden o 
no.
• En cada iteración del ciclo externo los elementos 0 a i forman una lista 
ordenada. 

ANÁLISIS DEL ALGORITMO.

•Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable. 
•Requerimientos de Memoria: Una variable adicional para realizar los intercambios. 
•Tiempo de Ejecución: Para una lista de n elementos el ciclo externo se ejecuta n­1veces. El ciclo interno se ejecuta como máximo una vez en la
primera iteración, 2 veces en la segunda, 3 veces en la tercera, etc.
Ventajas:
 
• Fácil implementación. 
• Requerimientos mínimos de memoria. 

Desventajas:
 
•Lento. 
•Realiza numerosas comparaciones. Este también es un algoritmo lento, 
pero puede ser de utilidad para listas que están ordenadas o semiordenadas, porque en ese caso realiza muy pocos desplazamientos.

CODIFICACIÓN EN C++

[pic]

3. MÉTODO DE  ORDENAMIENTO POR INSERCIÓN BINARIA

“El método de ordenación por 'inserción binaria'' es una mejora del 
método de  inserción directa. Para lograr esta mejora se recurre a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un elemento en la parte izquierda del arreglo, que ya se encuentra ordenado. Elresto del 
procedimiento es similar al de inserción directa, es decir, se repite este mismo 
procedimiento desde el segundo término hasta el último elemento.”
(Luis Joyanes Aquilar)  

CODIFICACIÓN EN C++

4. ORDENAMIENTO POR EL MÉTODO DE SHELL
El método Shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes. En el método de ordenación por inserción
directa cada elemento se compara para su ubicación correcta en el 
arreglo, con los elementos que se encuentran en la parte izquierda del
mismo. Si el elemento a insertar es más pequeño que el grupo de 
elementos que se encuentran a su izquierda, es necesario efectuar 
entonces varias comparaciones antes de su ubicación. Shell propone que las comparaciones entre elementos se efectúen con saltos 
de mayor tamaño pero con incrementos decrecientes, así, los elementos quedarán ordenados en el arreglo más rápidamente. El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos
observaciones:
1....