Java

Ordenamiento de Arreglos

El siguiente ejercicio permite apreciar la importancia de descomponer los problemas complejos en subproblemas más simples de resolver. La clase Sorter sirve para ordenar arreglos de números reales.

La clase Sorter se usa de la siguiente manera. Suponga que Ud. ha construido su arreglo mediante la declaración:

   double[] array= { 5.0, 10.0, -4.0, 15.0, 13.0, 46.0, -2.0};

Para ordenar arreglo se crea un objeto de la clase Sorter pasando como argumento el arreglo:

   Sorter sorter= new Sorter(array);

El objeto construido es un ordenador de arreglos de números reales. En este punto, el objeto sorter y la variable array referencian el mismo arreglo. La construcción de sorter no ordena todavía el arreglo. De hecho, el objeto posee métodos para desplegar el contenido del arreglo en pantalla:

   sorter.print();

El resultado de esta invocación será:

    5.0 10.0 -4.0 15.0 13.0 46.0 -2.0

Para ordenar el arreglo se invoca el método sort:

   sorter.sort();

Después de esta llamada el arreglo referenciado por array se encuentra ordenado. Si ahora se invoca sorter.print(), el resultado estará ordenado:

-4.0 -2.0 5.0 10.0 13.0 15.0 46.0

El diseño de la clase Sorter

El problema del ordenamiento ha sido descompuesto en los siguientes métodos:

Los métodos sort, quicksort y particionar ordenan el arreglo en base a intercambio de elementos (swap), comparación de elementos (compare) y el tamaño del arreglo (size).
El método swap recibe como argumento 2 enteros que corresponden a los índices de dos elementos en el arreglo. Este método intercambia estos elementos.
El método compare recibe como argumento 2 enteros que corresponden a los índices de dos elementos en el arreglo. Este método compara estos dos elementos y retorna -1 si el i-ésimo elemento es menor que el j-ésimo, 0 si son iguales y -1 si es mayor.
El método size simplemente retorna el tamaño del arreglo.

Ejercicio 1: Ordenamiento de strings

Este ejercicio consiste en modificar la clase Sorter de modo que ahora ordene arreglos de strings. La forma de usar esta clase será la siguiente:

    String[] array= {"pedro", "juan", "y", "diego"};
    StringSorter sorter= new StringSorter(array);
    sorter.sort();
    sorter.print();

El resultado de este programa debe ser:

    diego juan pedro y

Indicaciones:

Recupere la clase Sorter y compílela.
Pruebe la clase ejecutando el comando java PruSorter. La clase PruSorter ordena un arreglo de números reales.
Copie el archivo Sorter.java a StringSorter.java. Edite el archivo StringSorter.java y cambie el nombre de la clase a StringSorter.
Modifique el programa de modo que ordene un arreglo de strings. Para ello modifique adecuadamente:
- La declaración del arreglo:
  Cambie el tipo del arreglo double[] por String[].
- El constructor:
  Cambie el nombre del constructor Sorter por StringSorter. El argumento debe ser de tipo String[].
- El método swap:
  El tipo de la variable x ya no es double. Debe ser String.
- El método compare:
  Compare el i-ésimo elemento con el j-ésimo invocando el método compareTo de la clase String.
- Métodos size y print: no necesitan cambios.
No cambie los métodos sort, quicksort o particionar. El diseño de la clase coloca la parte compleja del problema en estos métodos. Estos métodos se abstraen del tipo de los elementos ordenados. Solo los métodos swap y compare toman en cuenta el tipo de los elementos del arreglo.

Compile su programa y pruébelo ejecutando:

    java PruStringSorter

R.-

Variante:

Modifique el programa de modo que ahora ordene descendentemente. En este caso Ud. sólo debe preocuparse de modificar el método compare.

Ejercicio 2: El algoritmo de ordenamiento

Cambie el algoritmo de ordenamiento por uno más simple como selección. En este caso, Ud. sólo debe cambiar el método sort (eliminando los métodos quicksort y particionar).

Pregunta filosófica: ¿Cómo se podría escribir una clase que sirva tanto para ordenar arreglos de números reales como arreglos de strings?

Solución: usando subclases. Estudie cuidadosamente el capítulo de subclases y luego realice los ejercicios que se proponen a continuación.

Ordenamiento genérico de arreglos

Decidme como intercambiar y comparar elementos y os ordenaré el mundo.

Uno de los problemas de los lenguajes tradicionales como Pascal o C es que se necesita un programa de ordenamiento para cada tipo de datos. En Java y otros lenguajes orientados a objetos es posible hacer un ordenador genérico, es decir que ordene cualquier tipo de datos.

Para lograr esto, se ha encapsulado la parte esencial del algoritmo de ordenamiento en una clase llamada GenSorter. Esta clase ordena los elementos de un arreglo sin considerar el tipo específico de sus elementos. El algortimo trabaja comparando e intercambiando los elementos del arreglo. Estas operaciones se realizan por medio de la invocación de métodos abstractos que deben ser definidos en una subclase de GenSorter.

Para utilizar esta clase, se hace necesario entonces definir una subclase de GenSorter en donde ser definen los métodos que faltan y que dependen del tipo específico de los elementos del arreglo. Estos métodos son compare, swap y size.

La clase GenSorter es una clase abstracta. Esto significa que contiene métodos sin implementar. No se pueden crear instancias de una clase abstracta (con new). Una clase abstracta existe sólo con el fin de definir subclases de ella en donde se implementen (mediante redefinición) los métodos que aparecen sin implementación en la clase abstracta.

Ejercicio 4: Reutilización de un Algoritmo de Ordenamiento

Coloque el archivo MultSorter.java en su directorio. Este archivo define dos subclases de GenSorter en donde se implementan los métodos compare, swap, size y print. La clase IntSorter sirve para ordenar ascendentemente arreglos de enteros y la clase DoubleSorterDesc ordena descendentemente arreglos de reales.
Examine ambos programas. Observe que en la clase IntSorter no se define el método sort y sin embargo se invoca. Esto es porque este método fue heredado de la clase GenSorter.
Compile MultSorter.java y ejecútelo.
Defina una subclase de IntSorter con el nombre IntSorterDesc que ordene un arreglo de enteros en orden descendente.
Para completar esta parte del ejercicio, Ud. sólo debe implementar un constructor para IntSorterDesc y redefinir el método compare. El resto de los métodos se heredan de IntSorterDesc.
Defina una subclase de GenSorter con el nombre StringSorter que ordene un arreglo de strings.
Para completar esta parte del ejercicio, Ud. debe declarar una variable de instancia para referenciar el arreglo que se ordenará, implementar un constructor para StringSorter y redefinir los métodos compare, swap, size y print.

R.-

Este es un patrón de diseño muy útil que se puede usar para implementar algoritmos y/o estructuras de datos que dependen de un conjunto pequeño de operaciones. La idea consiste en resolver distintas variantes del mismo problema, sin tener que reescribir todo el código nuevamente. El algoritmo general se escribe en una clase abstracta y las operaciones dependientes de los tipos de datos manejados se especifican en subclases.