Antes de empezar, repasar:

Más funciones

Trabajamos en un archivo funciones.c nuevo.

Definir la función int cuadrado(const int a) que calcula la función matemática : x ↦ x².

Llamarla desde el main sobre algun entero aleatorio entre -50 y 50:

int main(void){
  int a;
  srand(time(NULL));  /* inicializar la semilla del generador aleatorio */
  a = (rand() % 101) - 50;  /* a tiene un valor entre -50 y +50 */
  printf("a vale %d\n", a);
  printf("a^2 vale %d\n", cuadrado(a));
  return 0;
}

Definir la función int absoluto(const int a) que calcula la función matemática : x ↦ |x| (valor absoluto). Se puede hacer de la forma siguiente: si el parametro formal a es positivo, devolver a, sino, devolver −a.

Llamarla desde el main:

...
printf("|a| vale %d\n", absoluto(a));

Definir la función int mayor(const int a, const int b) que calcula la función matemática (x, y)↦{x si x ≥ y, sino y}.

Llamarla desde el main:

int b;
....
b = rand() %100; /* b tiene algun valor entre 0 y 99 */
...
printf("mayor(a, b) vale %d\n", mayor(a,b) );

Agregar al programa la función int mayor_abs(const int a, const int b) que calcula el payor del valor absoluto de dos enteros: (x, y)↦{|x| si |x|≥|y|, sino |y|}.

Importante: definir mayor_abs sin usar if/else, pero usando las funciones existentes mayor y absoluta.

...
printf("mayor_abs(a, b) vale %d\n", mayor_abs(a,b) );

Ámbito de las variables

Una variable local existe solo dentro de la funcion dentro de cual es definida. Los parámetros formales de una función también son variables locales.

Una variable global es una variable definida fuera de todas las funciones, y existe durante toda la duracion del programa.

Nosotros siempre vamos a definir variables locales, para que quede bien claro qué valores se transmiten entre las funciones.

Algoritmos de ordenamiento de arreglos

Considerar el programa ordenar.c siguiente:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX 10

void init(int a[]){
    int i;
    for (i=0; i<MAX; i = i+1){
        a[i] = i;
    }
}

/* https://es.wikipedia.org/wiki/Algoritmo_Fisher-Yates */
void mezclar(int a[]){
    int i,j,t;
    for(i=MAX-1; i>0; i = i-1){
        j = rand() % (i+1);
        t = a[j];
        a[j] = a[i];
        a[i] = t;
    }
}

int main(void){
    int lista[MAX];
    srand(time(NULL));
    init(lista);
    mezclar(lista);
    return 0;
}

¿Qué hace la función mezclar? ¿Cómo lo hace?

En ordenar.c, definir una función int ordenado(const int a[]) Tiene que devolver 1 (verdadero) si el arreglo está ordenado, sino 0 (falso).

Usar esta función en el main:

...
init(lista);
assert( ordenado(lista) );
mezcla(lista);
/* '!' es el operador de la negación lógica */
assert( ! ordenado(lista) );
...

Códigos de color ANSI

Usando printf con códigos especiales, se puede cambiar el color y el formato del texto mostrado en la shell.

Definimos tres macros:

#define FONDO_VERDE  "\x1b[102m"
#define FONDO_MAGENTA "\x1b[105m"
#define RESET         "\x1b[0m"

Así podemos usar la función siguiente que muestra la lista con colores. Se muestra con un color distinto cada elemento que es estrictamente menor al elemento que está ubicado a su izquierda.

void mostrar_color(const int a[]){
  int i;
  for(i=0; i<MAX; i=i+1)
    printf("%s%02d%s%s",(i<1||*(i+a)>=*(i-1+a))?FONDO_VERDE:
      FONDO_MAGENTA,a[i],RESET,(i<(MAX-1))?",":"");
  printf("\n");
}

No es necesario entender como funciona esta función ahora.

Agregar esta definición de la función mostrar_color al programa ordenar.c y llamarla desde el main.

...
init(lista);
assert( ordenado(lista) );
mostrar_color(lista);
mezclar(lista);
assert( ! ordenado(lista) );
mostrar_color(lista);
...

El problema de ordenar una lista

Tenemos el problema siguiente: dada una lista [a₁, a₁, a₂, …, a_n] de enteros, queremos devolver una lista [b₁, b₁, b₂, …, b_n] que satisface dos condiciones:

La lista de salida está ordenada (b₀ ≤ b₁ ≤ …...≤b_n).
La lista de salida es una permutación (o reordenamiento) de la lista de entrada (existe una función biyectiva p : [1..n]↦[1..n] tal que para todo i ∈ [1..n], a_i = b_p(i)).

Algoritmos de ordenamiento de lista

Existen muchos algoritmos de ordenamiento de listas. Se distinguen por varias características:

ciertos operan sin usar memoria externa (son in situ), mientras otros usan más memoria
ciertos tienen un mejor rendimiento que otros en velocidad
ciertos son más faciles de entender que otros

Vamos a ver algoritmos in situ que son fáciles de entender: selection sort y luego gnome sort.

Como son in situ, su implementación en el lenguaje C van a ser funciones que toman un arreglo como parámetro y lo modifican: void ordenar(int a[]).

Selection sort

En este video se puede ver un ejemplo de selection sort con naipes (no hace falta sonido):

Sea a la lista de entrada, de tamaño MAX. Una descripción de alto nivel del algoritmo sería:

buscar el mínimo elemento de la lista; sea k su índice
intercambiar el elemento de índice k con el elemento de índice 0
buscar el mínimo elemento en el resto de la lista (de la posición 1 a la posición MAX − 1); sea k su índice
intercambiar el elemento de índice k con el elemento de índice 1
buscar el mínimo elemento en el resto de la lista (de la posición 2 a la posición MAX − 1); sea k su índice
intercambiar el elemento de índice k con el elemento de índice 2
etc. repetir hasta el final de la lista

A medida que progresa el proceso, el tramo inicial de la lista se vuelve ordenado. Al final del proceso, toda la lista se encuentra ordenada.

Escribir este algoritmo en pseudocódigo.

Necesitamos usar dos índices:

i: indica la próxima posición que tiene que recibir el mínimo del resto de la lista
j: usamos para recorrer el resto (desordenado) de la lista para buscar el mínimo.

El algoritmo tiene un primer bucle que hace variar el índice i (¿de cuánto a cúanto?).

Adentro, tiene otro bucle que hace variar el índice j (¿de cuánto a cuánto?). Dentro de este segundo bucle, usamos una variable k para guardar el índice del elemento mínimo.

En ordenar.c, implementar el algoritmo en una función void selection_sort(int a[]) y usarlo en el programa que tenemos.

Imprimir la lista después del sort para asegurarse que queda ordenada.

Dentro de la función selection_sort imprimir la lista después de cada intercambio de valores.

Gnome sort

Ahora vemos un algoritmo distinto para resolver el mismo problema. La idea de este algoritmo es imaginarse un duende del jardín ordenando macetas. Los únicos intercambios que puede hacer son dos macetas una al lado de la otra. (Recordamos que con "selection sort", hacíamos intercambios de valores que podían ser lejos en la lista.)

El duende empieza por el principio de la lista (posición 0) y termina cuando llega al final:

si está mirando al primer elemento de la lista (a₀), o si el elemento que mira es mayor o igual al elemento que está justo a la izquierda (a_i > =a_i − 1), entonces hace un paso a la derecha sin intercambiar nada.
si el elemento que está mirando es menor al que está justo a la izquierda (a_i < a_i − 1), entonces intercambia los dos valores, y hace un paso a la izquierda.

El duende repite este proceso hasta que llegue al final de la lista.

Escribir el algoritmo del gnome sort. Pensar bien en cuál es la condición de repetición del bucle.

En ordenar.c, implementar el algoritmo en una función void gnome_sort(int a[]).

Dentro de la funcion gnome_sort, agregar una llamada* a color_ord después de cada intercambio de valores de la lista.

Para rematar

Probar aumentando el valor de la macro MAX para ver que todo sigue andando.

Para hacerlo más dramático, pueden agregar un system("sleep 1"); cada vez que muestran la evolución de las listas.

Entrega para la próxima semana

Entregar ordenar.c con todas la funciones pedidas (init, mezclar, ordenado y mostrar_color) y las llamadas y los assert adecuados desde el main, y:

si su nombre empieza con A, J, G, R, F o S: con selection_sort (gnome_sort es facultativo)
si su nombre empieza con C, D, K, O, P, B o M: con gnome_sort (selection_sort es facultativo)

Consignas antes de entregar su trabajo:

respetar los tipos de las funciones dados más arriba
su programa tiene que compilar sin errores ni warnings con gcc -Wall y clang -Wall
en cada función declarar todas las variables al principio
su programa no debe declarar ninguna variable ni arreglo global
todos los arreglos tienen como tamaño MAX
hacer las llamadas a mostrar_color en los lugares correctos
cuidar la presentación del código

Programación 1

2016-06-15