QUICK SORT

es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es la técnica de ordenamiento más rápida conocida. Fue desarrollada por C. Antony R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).





(Estos metodos de ordenamiento...han sido extraidos de:http://es.wikipedia.org/wiki/Ordenamiento_Radix)

SELECTION SORT

Es un algoritmo de ordenamiento que requiere O(n²) operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lísta
• Intercambiarlo con el primero
• Buscar el mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

HEAPSORT

El ordenamiento por montículos (Heap sort en ingles) es un algoritmo de ordenacion no recursivo, no estable, con complejidad computacional.

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un monticulo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

MERGESORT

Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann en 1945.

[Thomas Cormen, 2001].

Consiste en dividir en dos partes iguales el vector a ordenar, ordenar por separado cada una de las partes, y luego mezclar ambas partes, manteniendo el orden, en un solo vector ordenado.

El algoritmo MergeSort (u Ordenamiento por mezcla) es un algoritmo que sirve para ordenar secuencias de datos.

Utiliza los siguientes tres pasos:
DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2" elementos cada una.
VENCER: ordena las dos subsecuencias de manera recursiva mediante el algoritmo MERGESORT.
COMBINAR: combina las dos subsecuencias ordenadas para generar la solución.


ANÁLISIS

Como cualquiera de los algoritmos de ordenamiento recursivo tiene complejidad logarítmica: O(n log₂n).

Si el tiempo de ordenamiento de MergeSort para una lista de n elementos es T(n) entonces la repetición T(n) = 2T( n/2 ) + n sigue de la definición del algoritmo (Aplicar el algoritmo a las dos listas de la mitad del tamaño de la lista original y aumentar los n pasos tomados para utilizar MergeSort en las dos listas resultantes).

Algoritmo de ordenación :

Solución de la ecuación T (n) = 2T (n/2) + O(n)

FUNCIONAMIENTO

El proceso de este algoritmo es fusionar sucesivamente mitades ya ordenadas de datos:

El grupo de datos a ordenar es dividido en sus dos mitades pues es más sencillo ordenar una parte de los datos que el conjunto completo de ellos, cuando quede un solo dato en un subgrupo se termina el proceso de división pues ese subgrupo ya está ordenado. A continuación, se mezclan ambas mitades ordenando los datos a medida que se combinan, para ello se emplea un algoritmo sencillo que requiere un espacio auxiliar del tamaño del grupo original para añadir el dato correspondiente de cada subgrupo así:

Se comparan entonces los elementos de la mitad 1 en la posición pos1 y de la mitad 2 en la posición pos2, el menor se copia en ‘mezcla’ en la posición posMezcla, se incrementan las posiciones del origen que se ha copiado (pos1 o pos2) y la del espacio de destino (posMezcla) y se compara el nuevo par de elementos; finalmente alguna de las dos mitades habrá sido copiada completamente, entonces se debe copiar en el espacio de mezcla los elementos que hayan quedado sin copiar de la otra mitad.

El método de mezcla realiza un número de comparaciones que aumenta linealmente con el número de elementos a intercalar [Vicente López, 2001].

Este es un diagrama de árbol del funcionamiento del Algoritmo:

CARACTERÍSTICAS

La eficiencia de este algoritmo es bastante notable en tiempo de ejecución en comparación con otros, ya que su manera de trabajo por grupos pequeños agiliza la organización de los datos.

Su utilización se da con mucha frecuencia cuando la cantidad de registros no es muy grande ya que para hacer las mezclas éste método utiliza el doble del espacio que gasta el arreglo original de valores.

Este es un algoritmo estable (no intercambia los registros con claves iguales) dependiendo de la forma en que se implemente, recursivo y por tanto de complejidad O(n log₂n) tanto en el peor caso como en el mejor o en el caso promedio pues el tiempo que emplea no depende de la disposición inicial de los datos

VENTAJAS

A diferencia de algunas versiones mejoradas del QuickSort, MergeSort es un método estable de ordenamiento mientras la operación de mezcla (Merge) sea implementada correctamente.

Una gran ventaja del MergeSort es que su algoritmo tiene mucha estabilidad (se evitan los problemas de intercambio de claves en la manipulación de datos). En la gestión de Bases de Datos se utiliza comúnmente cuando la cantidad de registros en el índice es relativamente baja, ya que en caso contrario es poco productivo debido a que gasta el doble de espacio del que ocupan inicialmente los datos.

Este algoritmo es efectivo para conjuntos de datos que se puedan acceder secuencialmente como arreglos, vectores y listas ligadas

DESVENTAJAS

Su principal desventaja radica en que está definido recursivamente y su implementación no recursiva emplea una pila, por lo que requiere un espacio adicional de memoria para almacenarla.

A los algoritmos que realizan el proceso de ordenamiento dentro del mismo vector se les denomina algoritmos de ordenamiento "in-situ", el algoritmo de MergeSort no pertenece a esta familia ya que no utiliza el espacio sobre el que están almacenados los datos sino que para poder funcionar requiere de un espacio de memoria adicional del tamaño de los datos a ordenar en el cual se realicen las mezclas


(http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla)
(http://siona.udea.edu.co/~edatos2/MetAccUniDim/o_mergesort/teoria_mergesort_06.htm9)