Metodos de Ordenamiento

Métodos de Ordenamiento

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

Métodos de Ordenamiento Elementales:
1. Inserción
2. Selección
3. Burbujeo

Métodos de Ordenamiento no Elementales:
1. Shell
2. Quick Sort
3. Fusión

Tipos de Ordenamiento:
Ordenamiento Interno Ordenamiento de datos en Memoria Principal. (La lectura y grabación se hacen en registros)
Ordenamiento Externo  Ordenamiento de datos en Disco.

Tipos de Entrada de Datos:
a. Entrada Ordenada = MEJOR CASO
b. Entrada Orden Inverso = PEOR CASO
c. Entrada Desordenada = CASO AL AZAR

Tipos de Algoritmo
Algoritmo Sensible: Modifica su tiempo de ejecución según el tipo de entrada.
Algoritmo NoSensible: Su tiempo de ejecución es independiente al tipo de entrada.
Algoritmo Estable: Aquellos que teniendo clave repetida, mantiene su posición inicial igual a la final.
Algoritmo No Estable: Aquello que no respetan la posición inicial igual que la final teniendo claves repetidas





Métodos Elementales:

1. ORDENAMIENTO POR SELECCIÓN

DESCRIPCIÓN.
Buscas el elemento más pequeño dela lista.
Lo intercambias con el elemento ubicado en la primera posición de la lista.
Buscas el segundo elemento más pequeño de la lista.
Lo intercambias con el elemento que ocupa la segunda posición en la lista.
Repites este proceso hasta que hayas ordenado toda la lista.

ANÁLISIS DEL ALGORITMO.
Requerimientos de Memoria: Al igual que el ordenamiento burbuja, este algoritmo sólo necesitauna variable adicional para realizar los intercambios.
Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados.

Ventajas:
1. Fácil implementación.
2. No requiere memoria adicional.
3. Rendimiento constante: poca diferencia entre el peor y el mejor caso.

Desventajas:
1. Lento.
2. Realizanumerosas comparaciones.

2. ORDENAMIENTO POR INSERCIÓN DIRECTA

DESCRIPCIÓ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.
Sebasa 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 hacercomparaciones, 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 de comparació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 intercambiaregistros 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 n1 veces. 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:
1. Fácil implementación.
2....