Computación I

Ordenamiento Basado en Colas

Objetivos: Mostrar un algoritmo de ordenamiento simple, basado en el uso de colas.

Temas:

Construcción de colas.
Despliegue de los elementos de una cola.
Extracción del mínimo elemento de una cola.
Ordenamiento de los elementos de una cola.

Construcción de una cola

Problema

Se necesita una función leeCola que reciba como argumento el nombre de un archivo que contiene reales, lea su contenido y construya una cola con los reales leídos en el archivo. La función debe retornar la cola construida. Si el archivo reales.txt contiene los números:

   5.3, 1.2, 8.0, 4.5

entonces, leeCola("reales.txt") debe entregar una cola que contiene en primer lugar el 5.3, luego 1.2, 8.0 y 4.5 (en ese orden).

Solución:

    Queue leeCola(String arch) {
      Queue cola= new Queue();
      TextReader lect= new TextReader(arch);
      while (true) {
        double x= lect.readDouble();
        if (lect.eofReached()) {
          break;
        }
        cola.put(x);
      }
      lect.close();
      return cola;
    }

Despliegue de los elementos de una cola

Problema

Se necesita un procedimiento MuestraCola que despliega en pantalla los valores reales almacenados en una cola. El procedimiento debe dejar la cola en el mismo estado que la encontró.

Primera solución errada

    void muestraCola(Queue cola) {
      while (! cola.isEmpty())
        print(cola.getDouble()+" ");
      println();
    }

Este procedimiento despliega el contenido de la cola, pero también deja la cola vacía, después de la invocación de muestraCola. Esto se puede apreciar con el siguiente programa que usa leeCola y muestraCola:

    Queue reales= leeCola("reales.txt");
    println(reales.isEmpty()); // false
    muestraCola(reales);
    println(reales.isEmpty()); // true

La invocación de leeCola construye una cola con los reales 5.3, 1.2, 8.0 y 4.5 (en ese orden). La cola es referenciada por la variable reales. Luego, la primera invocación de muestraCola despliega:

    5.3 1.2 8.0 4.5

Pero como deja la cola vacía, la invocación reales.isEmpty() entrega verdadero. Esto se debe a que el procedimiento produce un efecto lateral indeseado en la cola. Esto es incorrecto porque en el enunciado del problema se pide que la cola quede en el mismo estado de antes de la invocación.

Esto se puede entender mejor recurriendo a la metáfora de los robots. La cola es un robot y la variable reales almacena el número del celular de ese robot. Al invocar el procedimiento muestraCola se le pasa como argumento es número de ese celular. El procedimiento envía órdenes al robot para que extraiga los elementos de la cola. El robot que recibe estas órdenes es el mismo que es conocido por medio de la variable reales. De modo que cuando el procedimiento retorna y entonces se pregunta al robot si la cola que administra esta vacía, éste responde que sí.

Segunda solución errada

A medida que se extraen los elementos de la cola, regresarlos al final de la cola:

    void muestraCola(Queue cola) {
      while (! cola.isEmpty()) {
        double x= cola.getDouble();
        print(x+" ");
        cola.put(x); // resgresamos el valor al final de la cola
      }
      println();
    }

Esta solución es incorrecta porque al agregar los elementos al final la cola nunca quedará vacía y por lo tanto el ciclo será eterno, desplegando en pantalla varias veces el contenido de la cola.

Tercera solución errada

La idea es construir una segunda cola e ir dejando los elementos en esa cola.

    void muestraCola(Queue cola) {
      Queue aux= new Queue();
      while (! cola.isEmpty()) {
        double x= cola.getDouble();
        print(x+" ");
        aux.put(x); // resguardamos los elementos en aux
      }
      println();
    }

Esta solución también es incorrecta, porque aún cuando los elementos quedan resguardados en la cola aux, esta cola es desconocida desde fuera del procedimiento. La variable reales usada como argumento en la invocación continuará referenciado el mismo robot al cual se ordenó extraer todos sus elementos.

Un típico error que se comete es agregar una línea que retorne la cola:

      return aux;

Esto es un error porque muestraCola ha sido definida como un procedimiento y no como una función, y por lo tanto, no puede retornar ningún valor.

Entre paréntesis, se podría definir que muestraCola sea una función mediante:

    Queue muestraCola(Queue cola) {
      Queue aux= new Queue();
      ...
      return aux;
    }

y luego reemplazar la invocación por:

    reales= muestraCola(reales);

Esto cambia la variable reales, almacenando el número del celular del nuevo robot que fue construido por la función muestraCola. Sin embargo, esta solución es poco elegante, porque los que usen la función (los que la invoquen) correrán el riesgo de olvidar la asignación y escribir simplemente:

    muestraCola(reales);

lo cual es legal en Java, pero deja la variable reales referenciando una cola vacía.

Primera solución correcta

La idea es que después de desplegar el contenido de la cola, se restaure su contenido, obteniéndolo de la cola aux.

    void muestraCola(Queue cola) {
      Queue aux= new Queue();
      while (! cola.isEmpty()) {
        double x= cola.getDouble();
        print(x+" ");
        aux.put(x); // resguardamos los elementos en aux
      }
      println();
      // ahora restauramos el contenido de cola
      while (!aux.isEmpty())
        cola.put(aux.getDouble());
    }

Esto dejará la cola aux vacía, pero no importa, porque esa cola es desconocida desde el exterior del procedimiento.

Segunda solución correcta

Esta solución se basa en la segunda solución errada, que agregaba los elementos al final de la cola, pero usa un método adicional que entrega el número de elementos que hay en una cola:

    int tamanno= cola.size(); // número de elementos en espera

Con este método podemos hacer que sólo se hagas las iteraciones que corresponden al número de elementos que hay originalmente en la cola:

    void muestraCola(Queue cola) {
      int tamanno= cola.size();
      int i= 1;
      while (i<=tamanno) {
        double x= cola.getDouble();
        print(x+" ");
        cola.put(x); // regresamos el valor al final de la cola
        i= i+1;
      }
      println();
    }

Extracción del mínimo elemento en una cola

No siempre se requiere extraer el elemento que está en primer lugar en una cola. En ocasiones se necesita extraer un elemento que cumpla una determinada propiedad, como por ejemplo el mínimo. En tal caso, hay que realizar esta extracción en términos de las operaciones que ofrece la cola.

Problema

Escriba una función double minimo(Queue cola) que recibe una cola con números reales y extrae y retorna el mínimo de la cola. Por ejemplo, si la cola tiene los valores:

    9 2 7 1 3 6

La función debe retornar el valor 1 y hacer desaparecer este valor de la cola. El orden en que quedan los demás elementos en la cola es irrelevante. La cola puede quedar por ejemplo como:

    9 7 2 3 6

Si el mínimo se encuentra repetido, sólo se debe extraer uno de ellos.

Solución correcta

Por simplicidad supondremos que la cola no está vacía. Para resolver el problema usaremos una variable real min que mantendrá el mínimo parcial a medida que se visitan los elementos de la cola. Entonces, procedemos de la siguiente forma:

Sea tamanno el número de elementos en la cola.
Extraemos el primer elemento de la cola y lo almacenamos en la variable min.
En seguida, extraemos el siguiente elemento y lo comparamos con min. Si es mayor, lo descartamos colocándolo al final de la cola. Si es menor, entonces descartamos el valor que está almacenado actualmente en min, colocándolo al final de la cola y almacenamos el valor recién extraído en min.
El paso anterior lo repetimos tamanno veces - 1.
Después de la última iteración, el mínimo de la cola original estará almacenado en min y la cola tendra tamanno-1 elementos (no contiene el mínimo).

Programa:

    double minimo(Queue cola) {
      int tamanno= cola.size();
      double min= cola.getDouble();
      int i= 1;
      while (i<tamanno) {
        double x= cola.getDouble();
        if (x>min) {
          cola.put(x);
        }
        else {
          cola.put(min);
          min= x;
        }
        i= i+1;
      }
      return min;
    }

Ordenamiento de los elementos de una cola

Problema

Se necesita un procedimiento que recibe como parámetro una cola con números reales y la ordene de menor a mayor. Por ejemplo, si la cola reales contiene:

    5.0, 3.0, 9.0, 7.0, 2.0

entonces después de invocar ordenar(reales), la cola debe contener:

    2.0, 3.0, 5.0, 7.0, 9.0

Solución

La idea es ir extrayendo el mínimo elemento de la cola y dejándolo en una cola auxiliar hasta que se vacíe la cola original. Al final, la cola auxiliar estará ordenada. Entonces, se transfieren todos los elementos de la cola auxiliar a la cola inicial, manteniendo el orden en el proceso.

    void ordenar(Queue cola) {
      // Construimos la cola auxiliar
      Queue aux= new Queue();
      // Hacemos un ciclo extrayendo el mínimo hasta vaciar la cola
      while (! cola.isEmpty())
        aux.put(minimo(cola)); // el mínimo lo agregamos al final de aux
      // Ahora aux está ordenada.
      // Transferimos los elementos de aux a cola.
      while (! aux.isEmpty())
        cola.put(aux.getDouble());
    }

Aplicación: ordenamiento de un conjunto de números reales contenidos en un archivo.

    Queue reales= leeCola("reales.txt");
    ordenar(reales);
    muestraCola(reales);

El algoritmo aquí presentado funciona correctamente, pero veremos más adelante que resulta muy ineficiente porque:

Extraer y agregar elementos en un cola es unas veces más lento que manipular elementos en un arreglo nativo de números reales. El programa podría tomar 100 veces menos tiempo si se colocan los números en un arreglo nativo y luego se ordenan en el arreglo.
El tiempo de ejecución crece proporcionalmente con el cuadrado del número de elementos que se ordenan. Estos son los tiempos que se obtienen en un Pentium 166MMX:

Número de Tiempo de
elementos ordenamiento
100 menos de 1 seg.
500 5 seg.
1000 20 seg.
2000 80 seg.
100000 2 dias

Número de	Tiempo de
elementos	ordenamiento
100	menos de 1 seg.
500	5 seg.
1000	20 seg.
2000	80 seg.
100000	2 dias

Observación:

El ordenamiento es el problema más frecuente en computación. De hecho, el 50% del tiempo de uso de un computador se destina a realizar ordenamientos de datos.

Pronto veremos mecanismos de ordenamientos mucho más eficientes.

Tarea

Escriba un programa que lea el archivo "nombres.txt" que contiene nombres de personas y los muestre en pantalla ordenados alfabéticamente. Por ejemplo si el contenido del archivo es:

    pedro
    ana
    juan
    patricia
    diego

El programa debe mostrar en pantalla:

ana diego juan patricia pedro
Ejercicio optativo
Defina una versión recursiva del procedimiento ordenar. Para ello, utilice el siguiente algoritmo:
Caso base:
Si cola esta vacía, se puede considerar que está ordenada, de modo que ordenar retorna de inmediato, sin hacer nada.
Invocaciones recursivas:

Extraiga un elemento de la cola inicial. Este elemento será considerado el pivote.

Construya dos nuevas colas. La primera cola se usará para almacenar elementos menores que el pivote, la segunda para elementos mayores o iguales al pivote.

Extraiga uno a uno los elementos que quedan en la cola inicial. Los elementos que son menores que el pivote, agréguelos al final de la cola de menores. Los elementos que son mayores o iguales, colóquelos en la cola de los mayores o iguales.

Ahora la cola inicial está vacía, pero sus elementos están almacenado en: la variable pivote, la cola con los elementos menores que el pivote y la cola con los elementos mayores o iguales que el pivote.

Ordene recursivamente la cola de menores. Este problema es obligatoriamente más simple que el problema inicial, porque esta cola contiene menos elementos que la cola inicial.

Ordene recursivamente la cola de mayores o iguales. Esta cola no contiene el pivote, y por lo tanto es de menor tamaño que la cola inicial.

Transfiera a la cola inicial: los elementos de la cola de menores, el pivote y los elementos de la cola de mayores, en ese orden.

Ahora la cola inicial se encuentra ordenada!
Este ejercicio puede resultar difícil desde un punto de vista conceptual, pero si Ud. logra realizarlo, Ud. ha comprendido perfectamente el concepto de recursividad.