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:


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:

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

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.