Post on 11-Aug-2015
transcript
Inserción Directa
• Como empieza?
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado.
Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). (arreglar)
• Cuando ya no se encuentran elementos (todos los elementos fueron
desplazados y este es el más pequeño).
Usa Variable Auxiliar
• Esto se debe a que en el algoritmo se necesita un dato (un numero en este caso) que vaya comparado con la siguiente posición dentro de la lista.
Complejidad
• Dentro de su complejidad, la inserción directa es estable ya que no utiliza tantos recursos.
Ventajas y desventajas
Ventajas: - Fácil Implementación- Los requerimientos de memoria son
mínimos. Desventajas:- Es un algoritmo de ordenamiento lento.- Realiza numerosas comparaciones.
Mergesort
• Como empieza?
Empieza con un arreglo con X cantidad de posiciones. Este se tiene que dividir en dos partes y luego otra vez en dos y
sucesivamente hasta tener todos los elementos separados
• Luego se tienen que comprar los elementos y se selecciona el menor. Se siguen comparando hasta que el arreglo quede acomodado.
Ventajas y Desventajas
• Ventajas:
-Método de ordenamiento estable mientras la función de mezcla sea implementada correctamente.-Muy estable cuando la cantidad de registros a acomodar es de índice bajo, en caso contrario gasta el doble del espacio que ocupan inicialmente los datos. -Efectivo para conjunto de datos a los que se puede acceder secuencialmente ( arreglos, vectores, etc.)
Desventajas
• Principal desventaja: está definido recursivamente. Si se deseara implementarla no recursivamente se tendría que emplear una pila y se requeriría un espacio adicional de memoria para almacenarla.