METODOS DE ORDENAMIENTO

METODOS DE ORDENAMIENTO
INTRODUCCION
El ordenamiento es una labor común que realizamos continuamente, en la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como unfin en sí 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 lasdemás.
Método Burbuja
Al algoritmo de la burbuja, para ordenar un vector de n términos, tiene que realizar siempre el mismo número de comparaciones:
Método Inserción
En el peor caso este método tomatiempo O(n2). Un punto interesante es que el mejor caso, ocurre cuando el arreglo se encuentra ordenado, en ese caso el tiempo es O(n).Requiere O(n²) operaciones para ordenar una lista de n elementos.Método Shell
Con esto, el método de ordenación por Incrementos consiste en hacer h-ordenaciones de a para valores de h decreciendo hasta llegar a uno. Su implementación original, requiere O(n2)comparaciones e intercambios en el peor caso, esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n).
Método Quick Sort
El procedimiento Quick Sortdescarta la filosofía de caso mejor, peor y medio de los algoritmos clásicos de ordenación, pues aquí tales casos no dependen de la ordenación inicial del vector, sino de la elección del pivot.
MétodoCounting Sort
Este método tiene la restricción de que sólo puede ser aplicado en elementos en un intervalo de a lo más k elementos, típicamente en números naturales en el rango de 1 a k. Su cota detiempo es de O(n + k).
CONCLUSIONES
Si bien con los métodos de Inserción y Selección se nota una mejora en los tiempos de ejecución, es el método Shell quien presenta el mejor rendimiento debido a que esuna modificación de los métodos de Inserción y Selección, ya que realiza “saltos grandes” que permiten ordenaciones múltiples. Esto se ve claramente demostrado en las pruebas de tiempo. Ahora bien...