Capítulo 10. Métodos de ordenamiento: Inserción

El algoritmo para el método de ordenamiento por inserción consiste en ir ubicando cada elemento en su posición. Esto quiere decir que en cada iteración i se obtiene una secuencia ordenada de i - 1 elementos en la primera parte del arreglo y se inserta el elemento de la posición i para que ahora la secuencia de i elementos quede ordenada.

 

El pseudocódigo del algoritmo es el que sigue:

 

 

 

Al igual que en caso del ordenamiento por selección, las operaciones de asignación y comparación están incluidas dentro de dos bloques "para" lo que finalmente se traduce en una complejidad temporal de O(n²)

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 9. Métodos de ordenamiento: Selección

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(n²)

 

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 8. Divide y Conquista (Parte IV)

En este capítulo veremos un nuevo ejemplo de aplicación de la técnica de DyC.

 

Problema

Sea A[1...n], n >= 1, un vector de enteros diferentes y ordenados crecientemente, tal que algunos de los valores pueden ser negativos. Diseñar un algoritmo que devuelva un índice natural k, 1 <= k <= n, tal que A[k] = k, siempre que tal índice exista.

Pseudocódigo



 

La letra C significa que ese bloque tiene una complejidad temporal constante.

 

Análisis de complejidad Temporal

Vemos que el tamaño de la entrada se reduce a la mitad, por lo tanto nos encuadramos en el Caso 2

 

a = 1

b = 2

k = 0

 

Notar que 'a' es igual a 1 porque nunca se ejecutan ambos bloques (si uno se ejecuta, el otro no)

 

Reemplazando estos valores de los parámetros el costo del método queda en O(log n)

 

En este ejemplo, pusimos como pre condición, que el vector de enteros estuviera ordenado en forma creciente. En los próximos capítulos veremos métodos de ordenamiento que utilizan la técnica de Divide y Conquista para ordenar una cadena.



Capítulo 7. Divide y Conquista (Parte III)

Continuando con la serie de DyC, veremos en este capítulo un ejemplo de aplicación para resolver un algoritmo que calcule potencias de aⁿ cuando n es potencia de 2.

Antes de aventurarnos a escribir el pseudocódigo, analicemos un poco qué ocurre para a⁸

Podemos ver que los subproblemas 1 y 2 son idénticos, entonces carecería de sentido (en realidad se verá que se desperdiciarían recursos) hacer ambos. 

Lo más conveniente es tomar una sola mitad y luego multiplicar el resultado por sí mismo. Ahora sí podemos adentrarnos en el pseudocódigo para resolver el problema

Para el análisis de complejidad temporal observamos que el tamaño de la entrada disminuye a la mitad cada vez lo cual nos estamos en presencia del Caso 2 para métodos recursivos.

Los valores de a, b y k son 1, 2 y 0 respectivamente. Finalmente vemos que el orden del método para calcular potencias de 2 es O(log n).

Si no hubiésemos simplificado una de las ramas, tendríamos 2 llamadas recursivas en lugar de una sola:

R1 <- CALCULAR_POTENCIA(a, n1)

R2 <- CALCULAR_POTENCIA(a, n1)

De esta forma, a = 2, lo que finalmente se traduce en O(n), es decir, una complejidad temporal mayor a la calculada anteriormente.

Capítulo 6. Divide y Conquista (Parte II)

Como vimos en el Capítulo anterior, la técnica de Divide y Conquista se basa en subdividir un problema en problemas más pequeños similares e independientes entre sí, resolver estos problemas más pequeños y posteriormente juntar esas soluciones parciales (las soluciones de los subproblemas) en una única solución al problema mayor.

Hemos analizado el caso de la Búsqueda Binaria donde se pedía como pre condición que la cadena de números estuviera ordenada. En los próximos capítulos analizaremos métodos de ordenamiento eficientes que utilizan la técnica DyC: MergeSort y QuickSort.

En este capítulo, emplearemos Divide y Conquista para resolver el problema de determinar si una cadena de números está o no ordenada. Presentamos a continuación el pseudocódigo

Para realizar el análisis de complejidad temporal, considerar que el método "obtenerSecuencia" es constante.

El algoritmo puede ser encuadrado entonces en el Caso 2 de métodos recurrentes, con lo cual si a = 2, b = 2 y k = 0, obtenemos un costo para el método de O(n)

En el próximo capítulo veremos algunos ejemplos más de aplicación para DyC