Me lo contaron y lo olvidé, lo leí y lo entendí, lo hice y lo aprendí.





lunes, 26 de septiembre de 2011

[Programación] Pseudo Ordenamiento de colas

EN un trabajo de la escuela tuve la "maravillosa" idea de usar una cola para el manejo de objetos. En su primera implementación tuvo éxito, pero después tuve la necesidad de usar la misma cola pero con los elementos ordenados de menor a mayor en base a cierto atributo... ¿Cómo hago eso sin alterar el funcionamiento de la cola? Bueno, pensé que si implementaba un método de ordenamiento de la cola y lo mandaba a llamar solo cuando necesitaba que la cola esté ordenada; justo de aquí surgió el verdadero problema: ¿Cómo ordenar una cola? Ya que el inicio de la cola no es forzosamente la posición 0 ni la posición final es la posición [tamaño_del_arreglo - 1]; puede empezar en cualquier posición y terminar en otra posición cualquiera y éstas posiciones varían durante toda la ejecución del programa. Entonces?
Es muy probable que se inventen millones de métodos para resolver este problema (dije probable); pero justo se me vino a la idea de que si necesito sacar los elementos en un orden, no es rotundamente necesario tener ordenada la cola, solo asegurarme que el objeto que voy a sacar es el más bajo (o más alto, según las necesidades) de la cola, ésto me simplifica muchas operaciones.

Bueno, comúnmente nosotros tenemos el método de sacar un objeto de la cola de la siguiente manera:

public Objeto sacarCola()
{
  Objeto a;
  if(delante<array.length-1)
  {
    delante++;
  }
  else
  {
    delante =0;
  }
  a=array[delante];  return a;
}

Vale, es sencillo y práctico, pero con unas cuantas correcciones se puede obtener una ilusión de ordenamiento de la cola para asegurarse de siempre sacar el objeto menor de la cola en cada vez.

Mi lógica es asegurarme en que el objeto en la posición delante sea el menor, de no ser así buscar el objeto que le sea menor y al final, que esté seguro de obtener el menor objeto, solo intercambio las posiciones del objeto menor con el del objeto en la posición delante.
Para lo anterior solo necesito hacer un recorrido desde el inicio del arreglo hasta el final y buscar cuál objeto es el menor de la cola.
Ahora, también es necesario no tomar en cuenta a los objetos que se suponen ya no deben estar en la cola (ésto por que es muy recurrido a no eliminarlos realmente de las cola, solo se excluyen). Ésto se arregla con que al sacar un objeto, lo ponga como NULL en la cola.

Mi algoritmo termina siendo el siguiente en un segundo método de sacar:

public Objeto sacarColaOrdenada()
{
  int referencia = delante;
  for(int i =0;i<array.length;i++)
  {
    if(array[i]!=NULL)
    {
      if(array[i]<array[referencia]
      {
        referencia = i;
      }
    }
  }


  Objeto intercambio;
  intercambio = array[delante];
  array[delante] = array[referencia]
  array[referencia] = intercambio;


   Objeto a;
  a=array[delante];
  array[delante]=null;
  if(delante<array.length-1)
  {
    delante++;
  }
  else
  {
    delante =0;
  }
  return a;
}

Parece complicado? Explico:
Lo que hago en el primer bloque (el for) es posicionar un indice de referencia (que servirá para indicar el supuesto objeto más bajo de valor) inicialmente en la posición delante. Luego con la variable i voy checando cada posición no nula (no nula por que más adelante, a la hora de sacar el objeto, lo elimino del array) si ésta posición es menor a la referencia, de ser así cambio la posición de referencia por la del índice y así me sigo hasta que termine el array.

En el segundo bloque solo hago el intercambio de objetos, el objeto en la posición delante se va a la posición que apunta referencia y viceversa.

La tercera parte es casi igual al método anterior de sacarCola salvo el detalle de que pongo como NULL la posición del objeto que voy a sacar para después no tomarlo en cuenta en próximas llamadas a la función.

Bueno, éste es mi método de Pseudo ordenamiento de colas, resulta económico para el procesador y versátil en cuestiones en donde no es realmente necesario tener la cola ordenada en todo momento.

No hay comentarios:

Publicar un comentario

Perfil Google+