Antes de estudiar los métodos de ordenamiento que utilizan la técnica de Divide y Conquista, centraremos nuestra atención en los métodos de selección e inserción.
El objetivo es analizar la complejidad temporal de estos métodos más clásicos a fin de justificar la utilización de técnicas más eficientes.
El método de ordenamiento por selección consiste en ir buscando el menor de los elementos, colocarlo en la primera posición de una cadena, luego buscar el menor de los restantes, colocarlo en la segunda posición y así sucesivamente hasta que la cadena quede ordenada.
Presentamos el pseudocódigo de este método:
Sin hacer un análisis muy detallado podemos observar que las operaciones de asignación y comparación están embebidas en dos bloques "para", lo cual ocasiona que la complejidad temporal del método de selección sea O(n2)
Fuentes:
Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.
No hay comentarios:
Publicar un comentario