Ordenamiento

INTRODUCCION
El ordenamiento es una labor común que realizamos cotidianamente, es un proceso tan común en nuestras vidas que no nos detenemos a meditar mucho en ello. Ordenar es meramente colocar información de una manera especial basándonos en un criterio de ordenamiento.
En la ciencia de la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin ensí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. El propósito principal de un ordenamiento es el de facilitar la búsqueda de información.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal querepresente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.
Conceptos Preliminares
Antes de comenzar a ver cada algoritmo vamos a ponernos de acuerdo en algunos conceptos, para que no haya confusiones:
Clave: La parte de un registro por la cual se ordena la lista. Por ejemplo, una lista de registros con campos nombre, dirección y teléfono sepuede ordenar alfabéticamente de acuerdo al nombre. En este caso los campos dirección y teléfono no se toman en cuenta en el ordenamiento.
Criterio de ordenamiento o de comparación: El criterio que utilizamos para asignar orden a los registros con base en una o más claves. De esta manera decidimos si un registro es mayor o menor que otro.
Registro: Un grupo de datos que forman la lista. Pueden serdatos primitivos enteros, caracteres, reales, etc., o grupos de ellos, que en C++ equivalen a estructuras de datos.
Cuándo APLICAR un método
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
Al estudiar algoritmos de todo tipo, no sólo de ordenamiento, es bueno tener una forma de evaluarlos antes de pasarlos a código. De esta manera podremosdecidir cuál se adapta mejor a los requerimientos de nuestro programa. Así que veamos estos aspectos:
Estabilidad: Cómo se comporta con registros que tienen claves iguales. Algunos algoritmos mantienen el orden relativo entre éstos y otros no. Veamos un ejemplo. Si tenemos la siguiente lista de datos:
(Nombre, Edad)
Pedro 19, Juan 23, Felipe 15, Marcela 20, Juan 18, Marcela 17
Ordenadaalfabéticamente por el nombre con un algoritmo estable quedaría así:
Felipe 15, Marcela 20, Marcela 17, Juan 23, Juan 18, Pedro 19
Un algoritmo no estable podría dejar a Juan 18 antes de Juan 23, o a Marcela 20 después de Marcela 17.
Tiempo de ejecución: La complejidad del algoritmo, que no tiene que ver con dificultad del algoritmo, mas bien con el rendimiento o la eficiencia del algoritmo. Es una funciónindependiente de la implementación o de los factores externos. Tendremos que identificar una operación fundamental que realice nuestro algoritmo, que en este caso es comparar. Ahora contamos cuántas veces el algoritmo necesita comparar. Si en una lista de n términos realiza n comparaciones la complejidad es O(n). Una medida de eficiencia es:
Contar el número de comparaciones
Contar el número demovimientos de ítems
Estos están en función del número de elementos a ser ordenados.
Un buen algoritmo de ordenamiento requiere de O(n log n) comparaciones.
Requerimientos de memoria: El algoritmo puede necesitar memoria adicional para realizar su labor. En general es preferible que no sea así, pero es común en la programación tener que sacrificar memoria por rendimiento.
Tipos de ordenamientosinternos
Los datos a ordenar están en memoria la principal RAM, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo.
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...