Ésta es una continuación de la pequeña guía1 de Java básico para Algoritmos, que empieza aquí

4. Hola Algoritmo!

En la sección 1 de la parte anterior ya vimos el Hola mundo de Java. Ahora implementemos algún algoritmo para ver cómo se podría hacer en Java. Vamos a implementar el particionado de Lomuto, utilizado para particionar arreglos en los llamados recursivos de QuickSort.

4.1. Lomuto

Como este es una guía de Java para Algoritmos, y no una guía de Algoritmos, intentaré explicar rápidamente lo que se quiere hacer. Digamos que tenemos el arreglo \(Arr\):

\[Arr = [21, 24, 1, 15, 42, 23, 18]\]

Escojamos un elemento en el arreglo (por simpleza, el primero). Llamémoslo el pivote. Se dice que \(Arr\) está particionado si todos los elementos a la izquierda de su pivote son menores que él, y todos los elementos a la derecha son mayores (o \(\geq\), qué se yo).

Entonces, una partición de \(Arr\) con el pivote 21 sería:

\[[1, 15, 18, 21, 23, 24, 42]\]

(Como el arreglo está ordenado, está particionado escogiendo cualquier elemento como pivote). Pero también podría ser:

\[[18, 15, 1, 21, 42, 24, 23]\]

Basta que todos los números de \(\{18, 15, 1\}\) estén a la izquierda, y \(\{24, 23, 42\}\) a la derecha.

El algoritmo de Lomuto lo que hace es mantener el pivote en la primera posición, ir guardando los menores y luego de ellos los mayores al pivote, como se ve en el siguiente diagrama:

\[\begin{array}{|c|c|c|c|} \hline piv & < piv \quad{\color{red} \rightarrow}& > piv \quad{\color{blue} \rightarrow}& {\color{green} \star}\bbox[gray, 5pt]{\text{sin procesar}} \\ \hline \end{array}\]

En cada iteración, se encuentra un nuevo elemento sin procesar (la \({\color{green} \star}\)).

Si el elemento es mayor que el pivote, basta incrementar en uno el índice de la flecha \({\color{blue} \rightarrow}\) y ya está dentro del conjunto de los elementos mayores.

Si el elemento es menor que el pivote, se mueve la flecha \({\color{blue} \rightarrow}\). Ahora el último elemento de los \(> piv\) (la \({\color{green} \star}\)) está en el conjunto equivocado. Para resolverlo, lo intercambiamos con el primer elemento de los \(> piv\). Esto tiene la gracia que está justo adelante del último elemento de los \(< piv\). por lo que basta incrementar en uno el índice de la flecha \({\color{red} \rightarrow}\) para estar en ese elemento.

Cuando se termina de recorrer el arreglo, basta intercambiar el pivote con el elemento que está en la posición de la flecha \({\color{red} \rightarrow}\). De esta forma, el pivote está entre todos sus menores, y todos sus mayores.

Listo, ¿se entendió?

Ah, una cosa más: si le pasamos un arreglo de largo 100, muchas veces vamos a querer que no nos particione todo el arreglo, sino que sólo nos particione los primeros 50 elementos y el resto los deje como están. O que nos particione de los elementos 26 al 50. En general, podemos querer:

\[\begin{array}{|c|c|c|} \hline \text{dejarlo como estaba} & i_p\qquad \text{particionar} \qquad i_u& \text{dejarlo como estaba} \\ \hline \end{array}\]

Entonces, la función que tenemos que implementar no sólo pide un arreglo, sino que también los índices del primer y del último elemento del subarreglo a particionar.

    static <algo> lomuto(int[] arr, int ip, iu) {
        ...
    }

¿Qué es ese <algo>? En general es basta con entregar el arreglo particionado, pero también queremos saber la posición donde quedó nuestro pivote. ¿Podemos retornar más de una cosa en una función? Esto ya es implementación.

4.2. Lomito2

Ahora hay que implementar el algoritmo. En la parte anterior ya tuvimos que recorrer un arreglo al crear la función stringArreglo, pero ahora hay que hacer un par de cosas más. Una de las cosas que vamos a tener que hacer es intercambiar elementos de un arreglo: dejar \(Arr[i]\) en \(Arr[j]\) y viceversa. Si bien es fácil implementar esto cada vez que lo necesitamos, ayuda mucho guardar todos estos procedimientos útiles en funciones, para abstraernos al pensar.

A continuación una implementación la función para intercambiar:

    static int[] intercambiar(int[] x, int i, int j) {
		int tmp = x[i];
		x[i] = x[j];
		x[j] = tmp;
        return x;
    }

No tiene mucha ciencia, pero es útil.

Ahora, para implementar un algoritmo que ya tenemos, el procedimiento es básicamente ser un traductor Humano-Java. Pensar cómo ser hace algo es gran parte del trabajo en la carrera. Traduciendo el algoritmo, una implementación podría ser la siguiente:

    static void lomutoPartition(int[] x, int ip, int iu) {
        //elegir el primero como pivote
        int pivote = x[ip];

        //inicializar indice de la flecha roja (i)
        int i = ip;

        //el indice j equivale a la flecha azul
        for(int j = ip + 1; j <= iu; ++j) {
              
            //si menor que pivote juntarlo con menores
            if( x[j] < pivote ) {
                i++;
                x = intercambiar(x, i, j);
            }
            System.out.print(""+ j +"                  ");
            System.out.println(stringArreglo(x));
        }

        //pivote a su posición final
        x = intercambiar(x, ip, i);

        // Ahora tenemos el arreglo listo en x
        // y el indice de donde quedo el pivote en i
	}

Ahora, ¿cómo hacemos en Java para retornar más de una cosa a la vez? Podemos usar un truco:

    class Lomuto {
        static int[] intercambiar(int[] x, int i, int j) { 
            ...
        }
    
        static String stringArreglo(int[] arr) {
            ...
        }

        static ArregloIndice lomutoPartition(int[] x, int ip, int iu) {
            //elegir el primero como pivote
            int pivote = x[ip];

            //inicializar indice de la flecha roja (i)
            int i = ip;

            //el indice j equivale a la flecha azul
            for(int j = ip + 1; j <= iu; ++j) {
                  
                //si menor que pivote juntarlo con menores
                if( x[j] < pivote ) {
                    i++;
                    x = intercambiar(x, i, j);
                }
                System.out.print(""+ j +"                  ");
                System.out.println(stringArreglo(x));
            }

            //pivote a su posición final
            x = intercambiar(x, ip, i);

            return new ArregloIndice(x,i);
	    }

        public static void main(String[] args) {
            int[] arr = {21, 24, 1, 15, 42, 23, 18};
            ArregloIndice arrind = lomuto(arr, 0, arr.length-1);
            System.out.println("Arreglo final: "+stringArreglo(arrind.arr));
            System.out.println("Posición final pivote: "+arrind.indice);
        }

    }

    class ArregloIndice {
        public int[] arr;
        public int indice;

        public ArregloIndice(int[] newArr, int newInd) {
            arr = newArr;
            indice = newInd;
        }
    }

Ahí no estamos corriendo ningún programa de la clase ArregloIndice, sólo estamos utilizando un objeto para guardar dos objetos en él. Y en el encabezado de lomuto, tenemos que explicitar que el tipo del objeto que retorna es ArregloIndice. Esto es un ejemplo de programa en Java nivel Algoritmos donde puede ser útil tener más de una clase.3

5. Entrada y Salida

Es muy bonito hacer programitas que uno los corra y muestre el resultado en pantalla sin más interacción, pero en las tareas de Algoritmos muchas veces te van a pedir leer entradas desde la terminal, o desde archivos, y quizás también escribir archivos (dudo).

Java es matraquero4. Hacer cosas que si bien parecen tan simples como leer desde la consola, involucran muchas líneas de código, que si bien tienen razones para estar ahí (son abstracciones bonitas, generalizan casos, qué se yo), son muuucho boilerplate para gente acostumbrada al

nombre = input("escribe tu nombre: ")

de Python5. Pero… hay que hacerlo no más. Partamos con lo más fácil

5.1. Argumentos

Aquí le vamos a encontrar sentido a una parte del encabezado que escribimos en todos los programas: el mantra public static void main string args. Resulta que podemos hacer esto con la variable args:

    class Saludador {
        public static void main(String[] args) {
            for (int i=0; i < args.length; i++) {
                System.out.println("Hola "+args[i]+"!");
            }
        }
    }

Si compilamos Saludador.java y lo corremos de la forma tradicional… no pasa nada. Pero, si lo corremos así:

    java Saludador Pedro    Juan Diego

vemos que nuestro programa le da la bienvenida a PJD. Da lo mismo la cantidad de espacios que coloquemos, nuestra terminal se encarga de pasarle a Java los argumentos, y Java los guarda en un arreglo de Strings. Cada vez que le coloquemos [] al final de un tipo < lo que sea >, creamos un nuevo tipo que significa arreglo de < lo que sea >.

¿Y si quiero pasarle espacios? Pues hay dos formas:

    java Saludador Pedro\ Urdemales "Diego Ramírez"

Ahí el programa nos saluda por separado las frases “Pedro Urdemales” y “Diego Ramírez”: en la primera, con el \ escapamos el espacio siguiente, para que la terminal no separe las palabras; en la segunda, la terminal reconoce la frase por las comillas.

Notar que todo lo que le pasemos vía terminal (y en general, practicamente cualquier método de entrada) va a ser un String, por lo que para reconocer números hay que hacer un paso extra. Por ejemplo, el Sumador:

    class Sumador {
        public static void main(String[] args) {
            int suma = 0;
            for (int i=0; i < args.length; i++) {
                suma += Integer.parseInt(args[i]);
            }

            System.out.println("Suma: "+suma);
        }
    }

Por supuesto, el sumador acepta java Sumador 4 8 15 16 23 42, pero si hacemos java Sumador 10 7 polera 4 es culpa nuestra el error de conversión.

5.2. Leer desde la terminal

Hay muchas formas de hacer esto en Java. Voy a usar la que utiliza BufferedReader por su extensibilidad para la parte de archivos; si buscas como funciona Scanner verás que es parecido, e incluye métodos para leer directamente ints y floats (ver documentación. Como ejemplo para leer desde la consola línea por línea, un programa que muestra la línea de mayor largo que se le ha entregado:

    import java.io.*; // BufferedReader, IOException, InputStreamReader

    class Mayor {
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            System.out.println("Escribe:");

            String s, slargo;
            slargo = "";
            int mayorLargo = 0;

            while ( (s = reader.readLine() ) != null ) {
                if (s.length() == 0) {
                    break;
                }
                if (s.length() > mayorLargo) {
                    slargo = s;
                    mayorLargo = s.length();
                }
            }

            System.out.println("El string más largo entregado fue '"+slargo+"'");
            System.out.println("  largo: "+mayorLargo);
            reader.close();
        }
    }

Ahora analicemos qué hace cada parte.

  • import java.io.*; importa las librerías de Java que vamos a utilizar: la clase BufferedReader nos da el lector que vamos a usar directamente, y IOException es una excepción que puede lanzar BufferedReader si algo sale mal.
  • ... throws IOException: Java es muy precavido, y si algo puede lanzar un error de forma planeada, nos obliga a avisarlo. En cualquier función en la que hubieramos utilizado el BufferedReader tendríamos que escribir el throws, o bien un try-catch.
  • BufferedReader reader... nos da, después de mucha burocracia, el lector que queremos. En la subsección siguiente veremos otro caso.
  • while ( (s = reader.readLine() ) != null ) Primero, esta línea es divertida porque demuestra que las asignaciones (algo = otra cosa) también son expresiones (algo = algomás = otracosa es válido), lo cual vas a ver mucho en PSS (si lo tomas). El método readline() de los objetos del tipo BufferedReader entregan, como su nombre lo dice, una línea de archivo… pero si se acaba el archivo, entregan null. Entonces, el cuerpo del while se va a recorrer siempre que siga habiendo líneas en la entrada.
  • if (s.length() == 0) break; Esto es importante. La función6 readLine() nos entrega una línea nueva sin el salto de línea (el famoso \n o \r\n si estás en Windows), así que si presionamos Enter en una línea vacía, el lector le va a entregar al programa una línea vacía (de largo 0). Si no tuviéramos este pedazo de código aquí, la única forma en que podríamos salir del while sería haciendo Ctrl+D (lo que representa un EOF en la stdin, haciendo que readline() retorne null).
  • reader.close(); simplistamente hace que Java le diga a tu sistema operativo que dejó de leer el archivo. Puede que en lectura no te importe mucho gastar recursos, pero acostúmbrate a escribirlo para cuando estés escribiendo archivos (dentro de otras cosas, el método close() en la escritura se encarga de flushear el contenido del búfer a la salida).
  • El resto de las líneas son sólo implementación de la funcionalidad del programa.

<puedes-saltarte-esto>

Es interesante el concepto de Entrada Estándar y Salida Estándar. En los sistemas operativos à la Unix, puedes jugar con orígenes y destinos de entradas y salidas. Por ejemplo, si hicieras

    java Mayor < archivo.txt

lo que el < le está diciendo a tu programa es que la stdin no va a ser la terminal, sino que utiliza como entrada el contenido de archivo.txt. En particular, podrías hacer:

    java Mayor < Mayor.java

con lo cual le estarías pidiendo al programa que identificara la línea más larga de su propio código fuente.

De manera análoga, puedes redirigir la stdout de esta forma:

    java Mayor > archivo.txt

y todo lo que se hubiera impreso en pantalla, aparecerá en el archivo recién creado (si ya existía, se sobreescribirá; cambia > por >> para escribir al final de un archivo en caso de que ya exista).

Y, uniendo ambas cosas, puedes hacer que el programa corra sin ninguna interacción con la terminal:

    java Mayor < Mayor.java > mayor_linea_de_mayor.txt

</puedes-saltarte-esto>

Algo muy común que piden hacer en las tareas de Algoritmos (y también en problemas de Progra competitiva) es cargar arreglos desde la stdin. Es típico el siguiente flujo: te dan un número \(N\) en la primera línea, luego en las siguientes \(N\) líneas te dan distintos arreglos, no necesariamente del mismo tamaño.

Como ejemplo, un programa que dado \(N\) arreglos, retorna la suma de cada uno:

    import java.io.*;

    class SumaArreglos {
        static int sumaArreglo(int[] arr) {
            int s = 0;
            for (int i=0; i<arr.length; i++) {
                s += arr[i];
            }
            return s;
        }

        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int arreglos[][];

            System.out.print("Ingresa la cantidad de arreglos: ");
            int n = Integer.parseInt(reader.readLine());
            arreglos = new int[n][];

            String arrString;
            String arrEls[];
            int largoArreglo;
            for (int p=0; p < n; p++) {
                System.out.print("Arreglo " + (p+1) + ": ");
                arrString = reader.readLine();
                arrEls = arrString.split(" ");
                largoArreglo = arrEls.length;

                arreglos[p] = new int[largoArreglo];
                for (int i=0; i < largoArreglo; i++) {
                    arreglos[p][i] = Integer.parseInt(arrEls[i]);
                }   
            }

            for (int p=0; p < n; p++) {
                System.out.print("Suma arreglo " + (p+1) + ": ");
                System.out.println(sumaArreglo(arreglos[p]));
            }

            reader.close();
        }
    }

Para separar el cada String de números “1 2 6 343 2 12” en un arreglo de Strings {“1”, “2”, “6”, “343”, “2”, “12”}, se utilizó el método split() que tienen los objetos de la clase String. Es muy buena idea revisar la documentación para ver si hay funcionalidades que te sirvan que puede que ya estén implementadas. Por ejemplo: para obtener un caracter de un String, uno no puede hacer:

    String str = "Hola"
    char c = str[1];

Pero viendo la documentación, uno puede averiguar que existe el método charAt que hace exactamente lo que buscamos:

    String str = "Hola"
    char c = charAt(1);

(Por el otro lado, para convertir de char a String, es tan fácil como hacer str = ""+c)

5.3. Leer y escribir archivos

Para leer desde archivos vamos a utilizar la misma clase BufferedReader. Adivina cómo se llama la clase que vamos a utilizar para escribir archivos.7. Para abrir los archivos en modo lectura/escritura, vamos a usar un par de clases que se llaman FileReader y FileWriter. Recomiendo encarecidamente que leas la documentación de Java. Al menos la de estas clases. Al menos la de FileWriter. Al menos la de este constructor de FileWriter.

Siguiendo la costumbre en las secciones anteriores, vamos a ver un ejemplo de un programa que utiliza lectores y escritores de archivos. Este contador de palabras lee un archivo de texto y cuenta la cantidad de palabras de cada línea del archivo, escribiendo en un archivo de salida la cantidad de cada línea.

    import java.io.*;

    public class WordCounter {
        public static void main(String[] args) throws Exception {
            // Exception: IOException, FileNotFoundException,
            if (args.length < 2) {
                System.out.println(" Uso: java WordCounter <archivo_entrada> <archivo_salida> ");
                return;
            }

            String inputFileName = args[0];
            String outputFileName = args[1];

            BufferedReader reader = new BufferedReader(new FileReader(inputFileName));
            BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName));

            String inputLine;
            int numberOfWords;
            while ((inputLine = reader.readLine()) != null) {
                // en inputLine esta cada linea del archivo
                numberOfWords = inputLine.split(" ").length;
                writer.append(""+numberOfWords+"\n");
            }
            
            reader.close();
            writer.close();
        }
    }

Aquí estamos usando argumentos para recibir dos parámetros, el archivo de entrada (cuyas palabras vamos a contar) y el archivo de salida. Si tuviéramos el siguiente archivo de prueba test.txt

Lorem ipsum dolor
sit
amet, consectetur adipiscing elit,
sed
do eiusmod tempor incididunt ut
labore et dolore magna aliqua. Ut enim ad minim
veniam, quis...

Haciendo java WordCounter test.txt salida.txt en el archivo de salida veríamos

3
1
4
1
5
9
2

¿Cómo funciona? Pues bien, en los códigos de la sección 5.2 probablemente notaste que para obtener un lector hacíamos

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

Si lees la documentación de FileReader, verás que dice public class FileReader extends InputStreamReader. Esto quiere decir que FileReader es un tipo particular de InputStreamReader. En general un InputStreamReader (o “Lector de flujos de entrada”) toma como argumento un flujo de entrada, como lo es System.in8; en cambio, FileReader toma como parámetro un objeto File, o un String con el nombre del archivo a leer.

La historia del BufferedWriter y el FileWriter es muy similar: es más, es tan análogo, que si reemplazáramos la línea de BufferedWriter por

    BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

imprimiríamos en pantalla la salida en vez de escribir en el archivo.

Creo que hay dos o tres cosas más que vale la pena mencionar sobre el código y las funciones6:

  • Escribí throws Exception en vez de escribir el IOException que puede lanzar el BufferedWriter, y el FileNotFoundException que puede lanzar el FileReader.
  • El objeto FileWriter también puede construirse usando FileWriter(stringNombreArchivo, boolAppend), donde si el parámetro boolAppend es verdadero, el archivo en vez de sobreescribirse, va a ser escrito a partir de la última línea de lo que había antes (si existía); esto sale en la documentación. Es equivalente al open(stringNombreArchivo, 'w') de Python.
  • Si olvidas el writer.close(), no se va a escribir nada en el archivo (o no se va a imprimir nada en pantalla), ya que estamos escribiendo a un búfer de memoria (por eso la clase se llama BufferedWriter), y dentro del close() se flushea el búfer al archivo/pantalla.

Creo que esto es suficiente para esta parte (el post pesa casi 25 KB en Markdown!). A mi gusto, se me quedaron varias cosas en el tintero, como profundizar el crear clases y métodos de instancia (los cuales son útiles para la tarea 4, que hasta donde yo sé siempre es sobre Árboles). De todas formas, me parece que hay código rescatable para copypastear9 en vez de perder días intentando hacer funcionar soluciones de Google que no son lo que buscas.

Notas al pie

  1. No tengo la más remota idea de cuál es el diminutivo de guía. ↩

  2. No tengo ninguna razón para llamar así a esta subsección. Tampoco tengo razón para no hacerlo :P ↩

  3. Otra opción podría haber sido crear un arreglo de largo \(N+1\), donde el primer elemento fuera el índice, y el resto fuera el arreglo… pero tienes que admitir que se ve feo ↩

  4. De la cuarta acepción de matraca ↩

  5. Python 3.x, obvio. No hagas tal de no usar raw_input en Python 2.x. O de usar Python 2.x. ↩

  6. Que Bergel me pille confesado por decirles “funciones” a los métodos… ↩ ↩2

  7. BufferedWriter 🙄. ↩

  8. System.in no es más que el flujo de entrada que viene directamente desde la stdin. ↩

  9. Cuidado con MOSS. ↩