viernes, 20 de marzo de 2009
QUICK SORT
(Estos metodos de ordenamiento...han sido extraidos de:http://es.wikipedia.org/wiki/Ordenamiento_Radix)
SELECTION SORT
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.
jueves, 12 de marzo de 2009
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 log2n).
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:
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.
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.
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.
(http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla)
(http://siona.udea.edu.co/~edatos2/MetAccUniDim/o_mergesort/teoria_mergesort_06.htm9)