Miércoles 22 de Septiembre

Ordenamiento Genérico de Arreglos

Temas:

Ordenamiento Genérico

Hasta el momento, cada vez que necesitamos ordenar algún tipo de arreglo debemos programar un nuevo procedimiento de ordenamiento. Esto es desventajoso porque corremos el riesgo de cometer errores que se podrían evitar si pudiésemos escribir una vez el algoritmo de ordenamiento y poder reutilizarlo con distintos tipos de arreglos.

Esto se puede lograr gracias al concepto de subclases. La idea consiste en definir una clase que encapsule el algoritmo de ordenamiento En esta clase se dejan pendiente las operaciones de las cuales depende el algortimo de ordenamiento. La metodología toma real sentido cuando se definen susclases que redefinen las operaciones faltantes.

La examinar los distintos algoritmos de ordenamiento se puede observar que la parte dependiente del tipo de arreglo se encuentra en:

Entonces podemos colocar estas partes en métodos de la clase base que incluye el algortimo de ordenamiento. Estos métodos quedan en blanco a la espera que se redefinan en las subclases. A modo de ejemplo definiremos una clase que encapula el ordenamiento por selección y reemplazo. La clase base para el ordenamiento queda entonces como:

    class Ordenador extends Program {
      void seleccion(int n) { // n: número de elementos en el arreglo
        int i= 0;
        while (i<n) {
          // Buscamos la posicion del minimo en a[i], a[i+1], ..., a[n-1]
          int k= i;
          int j= i+1;
          while (j<n) {
            if (comparar(j, k)<0)
              k= j;
            j= j+1;
          }
          // intercambiamos a[i] con a[j]
          intercambiar(i, j);
          i= i+1;
        }
      }
      int comparar(int i, int j) {
      }
      void intercambiar(int i, int j) {
      }
    }

Subclases para ordenar arreglos de tipos primitivos

La clase Ordenador es en sí inútil. La idea es crear subclases de ella para definir el arreglo que se pretende ordenar y el cómo se comparan e intercambiar sus elementos. Por ejemplo, para ordenar un arreglo de enteros se define la siguiente subclase:

    class OrdenadorInt extends Ordenador {
      int[] a;
      OrdenadorInt(int[] a) {
        this.a= a;
      }
      int comparar(int i, int j) {
        if (a[i]<a[j])
          return -1;
        if (a[i]>a[j])
          return 1;
        return 0;
      }
      void intercambiar(int i, int j) {
        int aux= a[i];
        a[i]= a[j];
        a[j]= aux;
      }
    }
Para ordenar un arreglo se debe crear una instancia de la clase OrdenadorInt y luego invocar el método seleccion:

    int[] a= new int[10];
    a[0]= ...;
    a[1]= ...;
    ...
    OrdenadorInt ord= new OrdenadorInt(a);
    ord.seleccion(10);
La dos últimas instrucciones se pueden abreviar en una sola:

    new OrdenadorInt(a).seleccion(10);

Ejercicio: arreglos de strings El arreglo nombres contiene n nombres que deben ordenarse según el orden lexicográfico. Para realizar el ordenamiento se define una subclase de Ordenador:

    class OrdenadorString extends Ordenador {
      String[] s;
      OrdenadorString(int[] s) {
        this.s= s;
      }
      int comparar(int i, int j) {
        if (s[i]<s[j])
          return -1;
        if (s[i]>s[j])
          return 1;
        return 0;
      }
      void intercambiar(int i, int j) {
        String aux= s[i];
        s[i]= s[j];
        s[j]= aux;
      }
    }
Para ordenar el arreglo de nombres basta ejecutar:

    new OrdenadorString(a).seleccion(10);

Subclases para ordenar arreglos de objetos

La clase Persona se define como:

    class Persona extends Program {
      String nombres;
      String apellidos;
      int edad;
      double peso;
      ...
    }
Se dispone de un arreglo de n personas. Para ordenar este arreglo lexicográficamente primero por apellidos y luego por nombre se define la siguiente subclase:

    class OrdenadorPersona extends Ordenador {
      Persona[] personas;
      OrdenadorString(int[] personas) {
        this.personas= personas;
      }
      int comparar(int i, int j) {
        int cmp= compare(personas[i].apellidos, personas[j].apellidos);
        if (cmp<0)
          return -1;
        if (cmp>0)
          return 1;
        cmp= compare(personas[i].nombres, personas[j].nombres);
        if (cmp<0)
          return -1;
        if (cmp>0)
          return 1;
        return 0;
      }
      void intercambiar(int i, int j) {
        String aux= personas[i];
        personas[i]= personas[j];
        personas[j]= aux;
      }
    }
Ahora se desea ordenar el mismo arreglo por edad. Como la clase OrdanedorPersona ya incluye la definición adecuada del arreglo y el intercambio se puede definir una subclase de OrdenarPersona:

    class OrdenadorPersonaXEdad extends OrdenadorPersona {
      // El arreglo se hereda
      OrdenadorString(int[] personas) { // Los constructores no se heredan
        this.personas= personas;
      }
      int comparar(int i, int j) {
        if (personas[i].edad<personas[j].edad)
          return -1;
        if (personas[i].edad>personas[j].edad)
          return 1;
        return 0;
      }
      // El metodo intercambiar se hereda
    }
Ejercicio:

Ordene el arreglo de personas primero descendentemente por edad y ascendentemente por peso cuando las edades coinciden.