Computacion II: Algoritmos de Ordenamiento y Recursion

Ordenar es simplemente colocar información de una manera especial en base a un criterio de ordenamiento. En computación el ordenamiento de datos cumple un rol importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas de ordenamiento, cada una con características específicas, y con ventajas y desventajas sobre las demás.

Conceptos Preliminares

• Clave: La parte de un registro por la cual se ordena la lista. Por ejemplo, una lista de registros con campos nombre, direccion y telefono se puede ordenar alfabéticamente de acuerdo a la clave nombre. En este caso los campos direccion y telefono no se toman en cuenta en el ordenamiento.
• Criterio de ordenamiento (o de comparación): EL criterio que utilizamos para asignar valores a los registros con base en una o más claves. De esta manera decidimos si un registro es mayor o menor que otro. En el pseudocódigo presentado más adelante simplemente se utilizarán los símbolos < y >, para mayor simplicidad.
• Registro: Un grupo de datos que forman la lista. Pueden ser datos atómicos (enteros, caracteres, reales, etc.) o grupos de ellos, que en C equivalen a las estructuras.

Algunas convenciones sobre el pseudocódigo:

• La lista se ordena en forma ascendiente, es decir, de menor a mayor. Es esencialmente lo mismo que hacerlo en forma inversa.
• La forma de intercambiar los elementos depende de la estructura de datos: si es un arreglo es necesario guardar una copia del primer elemento, asignarle el segundo al primero y el temporal al segundo (swap). La variable temporal es necesaria, porque de lo contrario se perdería uno de los elementos. Si la estructura es una lista dinámica el procedimiento es parecido, pero se utilizan las direcciones de los elementos. En el pseudocódigo se utilizará el primer método.
• La lista se manejará como un arreglo de C: si tiene TAM elementos, el primer elemento es lista[0] y el último es lista[TAM-1]. Esto será así para todo el pseudocódigo presentado en este artículo.

Algoritmos más comunes.

• Ordenamiento Burbuja (Bubblesort)

• Ordenamiento por Selección

• Ordenamiento por Inserción

• Ordenamiento Rápido (Quicksort)

NOTA: Este articulo sobre ordenamiento es una version simplificada del artículo sobre Ordenamiento por Julian Hidalgo [C con Clase]. Los enlaces explicativos de cada algoritmo, son enalces directos al mencionado articulo

Recursion

Se dice que una función es recursiva cuando se define en función de si misma. No todas las funciones pueden llamarse a si mismas, deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente.

C permite la recursividad. Cuando se llama a una función, se crea un nuevo juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros en la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales, cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continua la ejecución en el punto en que había sido llamada.

Ejemplo

El ejemplo más típico de recursion es el factorial de n (n!). Esta función se define de la forma siguiente: Si n es igual a 0, entonces n! es igual a 1. Si n es mayor que 0, entonces n! es igual al producto de (n-1)! y n. Entonces, n! se define en términos de (n-1)!, que a su vez está definido en términos de ((n-1)-1)!, y así sucesivamente. Después de n pasos, n! está definido en términos de 0!, pero como 0! es igual a 1, no hay necesidad de continuar. Hagamos un ejemplo:

4! = 4*3! = 4*(3*2!) = 4*(3*(2*1!)) = 4*(3*(2*(1*0!))) = 4*(3*(2*(1*1))) = 4*(3*(2*1)) = 4*(3*2) = 4*6 = 24.

Por cierto, el factorial de n cuenta el número de permutaciones de n objetos distintos colocados a lo largo de una línea recta.

A continuación mostramos la frunción recursiva, en C para calcular el factorial de un entero:

 
int factorial(int n)
{
   if (n == 0) 
      return 1;
   else 
      return n*factorial(n-1);
}

int main ()
{

printf ("%d\n", factorial(4));
return 0;

}

Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial(4):

1ra Instancia 
n=4 
salida -> 4 * factorial(3) (Guarda el valor de n = 4) 

	2da Instancia 
	salida -> 3*factorial(2) (Guarda el valor de n = 3) 

		3da Instancia
		salida -> 2*factorial(1) (Guarda el valor de n = 2) 

			4ta Instancia
			n == 1 -> retorna 1 

		3ra Instancia 
		(recupera n=2 de la pila) retorna 1*2=2 

	2da instancia 
	(recupera n=3 de la pila) retorna 2*3=6

1ra instancia
(recupera n=4 de la pila) retorna 6*4=24
valor de retorno -> 24

Discusión

• Una función recursiva es una función que se llama a sí misma ya sea de manera directa o indirecta
• Si una función recursiva es llamada con un caso base, la función simplemente regresa un resultado. Si la función es llamada con un problema mas complejo, la función divide al problema en dos partes conceptuales: una parte que la función sabe como ejecutar, y una versión ligeramente más pequeña del problema original. Dado que este nuevo problema se parece al problema original, la función emite una llamada recursiva, para trabajar en el problema menor.
• Para que termine una recursión, cada vez que la función recursiva se llama a sí misma, con una versión ligeramente más simple del problema original, la secuencia de problemas más y más pequeños debe converger al caso base. Cuando la función reconoce al caso base, el resultado es regresado a la llamada de función previa, y a continuación sigue una secuencia de regresos hacia atrás, hasta que la llamada original de la función eventualmente devuelve el resultado final.

Analogía

Puede hacerse una analogía entre la recursión y las muñecas Rusas de madera que tienen siempre una muñeca mas pequeña en su interior. Cada muñeca "llama" a otra muñeca, y puede pensarse que el tamaño de la muñeca es un contador que se va decrementando en 1. Cuando se llega a la muñeca mas pequeña, que no puede abrirse mas, se termina la recursión. Normalmente una función recursiva tiene una variable que realiza una acción similar. Es decir, una variable que controla cuando finalmente la función termina. La condición donde la función no se llama a si misma se denomina el caso base de la función. Basicamente, es una instrucción if que chequea alguna variable por una condición. Si esta condición es verdadera, la función no se llamará a sí misma

Otro Ejemplo: Los Conejos de Fibonacci

Un matemático italiano conocido como Fibonacci, propuso el siguiente problema: Suponga que compramos una pareja de conejos adultos. Al cabo de un mes, esa pareja tiene una pareja de conejitos (un conejo y una coneja). Un mes después, nuestra primera pareja tiene otra pareja de conejitos (nuevamente, un conejo y una coneja) y, al mismo tiempo, sus primeros hijos se han vuelto adultos. Así que cada mes que pasa, cada pareja de conejos adultos tiene una pareja de conejitos, y cada pareja de conejos nacida el mes anterior se vuelve adulta. La pregunta es, ¿cuántas parejas de conejos adultos habrá al cabo de n meses? Para resolver este problema, llamemos Fn al número de parejas adultas al cabo de n meses. No es difícil convencerse de que si n es al menos 2, entonces Fn es igual a Fn-1 + Fn-2. Así que Fn queda en términos de Fn-1 y Fn-2, que a su vez quedan en términos de Fn-2, Fn-3 y Fn-4, y así sucesivamente. Para determinar el caso base, recordemos que al principio había una pareja de conejos adultos, la misma que había al final del primer mes, así que F0 = F1 = 1. Hagamos un ejemplo:

F4 = F3 + F2 = (F2 + F1) + (F1 + F0) = ((F1 + F0) + 1) + (1 + 1) = ((1 + 1) + 1 ) + 2 = (2 + 1) + 2 = 3 + 2 = 5

La sucesión de números F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, etc. recibe el nombre de sucesión de Fibonacci.

A continuación mostramos la funcióne recursiva en C, que resuelve el problema de Fibonacci.

      
int fib(int n)
{
   if ((n == 0) || (n == 1)) 
      return 1;
   else 
      return fib(n-1) + fib(n-2);
}
    

Relación entre Recursión e Iteración

• Tanto la iteración como la recursión:
  • se basan en una estructura de control: la iteración utiliza una estructura de repetición y la recursión una estructura de selección.
  • incluyen repeticion: la iteración utiliza una estructura de repetición de forma explícita; mientras que la recursión consigue la repetición mediante llamadas de función repetidas.
  • incluyen una prueba de terminación: la iteración termina cuando falla la condición de continuación del ciclo; la recursión termina cuando se reconoce el caso base.
  • pueden ocurrir de forma infinita: la iteración se puede quedar en ciclo infinito si la condición del ciclo nunca se hace falsa; la recursión se hará infinita si el paso de recursión no reduce el problema de tal forma que converja al caso base.
• La recursión invoca de manera repetida, y por lo tanto, puede sobrecargar las llamadas de función. Esto puede resultar costoso tanto en tiempo de procesador como en espacio de memoria.

Ir a Pagina del Curso