public abstract class GenSorter {

  // El algoritmo de ordenamiento.  Este algoritmo no es relevante.
  // Lo unico importante es que el codigo no referencia en ningun instante
  // el arreglo mismo.  Siempre trabaja con los indices.  Para intercambiar
  // elementos en el arreglo, se invoca el metodo swap, pasando como argumentos
  // los indices que deben ser intercambiados.  Analogamente, para comparar
  // los elementos, se invoca el metodo compare.
  public void sort() {
    quicksort(0, size()-1);
  }
  
  void quicksort(int i, int j) {
    if (i>=j)
      return; 
    int k= partition(i, j);
    quicksort(i, k-1);
    quicksort(k+1, j);
  }
  
  int partition(int i, int j) {
    int k= i; 
    i++;
    for(;;) {
      while (i<j && compare(i,k)<=0)
        i++;
      while (i<j && compare(j,k)>=0)
        j--;
      if (i==j)
        break;
      swap(i,j);
    }
    if (compare(k,i)<0)
      i--;
    swap(k,i);
    return i;
  }

  // Las componentes modulares del algoritmo
  // ---------------------------------------

  // Redefina los siguientes métodos para que el método sort pueda
  // realizar el ordenamiento.  En esta clase los métodos son abstractos
  // lo que quiere decir que ellos deben ser definidos en las subclases
  // de GenSorter.

  // Defina aquí el método swap
  // argumentos: dos índices de elementos en el arreglo array
  // acción: los intercambia
  // resultado: nada
  public abstract void swap(int i, int j);

  // Defina aquí el método compare
  // argumentos: dos índices de elementos en el arreglo array
  // acción: los compara
  // resultado: -1 si el primero es menor que el segundo, 0 si son iguales
  //   y 1 si es mayor
  public abstract int compare(int i, int j);

  // Defina aquí el método size
  // argumentos: ninguno
  // acción: ninguna
  // resultado: retorna el número de elementos del arreglo
  public abstract int size();

  // Redefina este metodo para desplegar en pantalla el arreglo
  public abstract void print();
}