Ordenamiento de listas enlazadas Leandro Rabindranath León

A veces creo que nunca se tiene suficiente edad para dejar de ser soberbio. El miércoles pasado, durante mi clase de Estructuras de Datos, explicando recursión y maneras de convertir algoritmos recursivos a versiones no recursivas, aproveché para explicar el célebre método de ordenamiento quicksort sin recursión. Se me ocurrió preguntar a mis estudiantes acerca de cuál tipo de secuencia preferían: arreglos o listas enlazadas. No había de terminado de enunciar la propuesta cuando me percaté de que jamás había yo pensado sobre ese problema particular y que a lo mejor me sería difícil deducir tal algoritmo.

Mis estudiantes seleccionaron listas. Les aclaré la verdad recién aprehendida; o sea, que nunca había enfrentado ese problema particular. Cavilé unos instantes; pensé: has resuelto problemas más difíciles, dominas el quicksort, especialmente la versión no recursiva con arreglos, y bueno .. hacía años me encantó estudiar y programar ordenamientos. Pues vamos a entromparlo, como se dice ...

Durante unos 40 minutos traté de deducir un algoritmo que no apelase a la simple emulación de recursión. No lo logré. Algo muy positivo fue que tuve toda la colaboración de los estudiantes. Creo que algunos se pusieron a pensar intensivamente e inclusive y aportaron observaciones muy interesantes.

Así pues, vamos a ver como se instrumenta el quicksort sobre listas enlazadas y sin recursión. El código emplea Aleph-w especialmente el tipo Dnode<T>. Por simplicidad en mis pruebas, el código se muestra sobre Dnode<int>.

1  Quicksort recursivo

Puesto que el quicksort es un algoritmo dividir/combinar, es conveniente entender la versión recursiva .

Échemosle una mirada a la versión Aleph

template <class Compare> 
void quicksort(Dlink & list) 
{
  if (list.is_unitarian_or_empty()) 
    return;

  Dlink * pivot = list.remove_next();
  Dlink smaller, bigger; // listas de menores y mayores que pivot

  // particionar lista

  quicksort <Compare> (bigger);  
  quicksort <Compare> (smaller);

  list.concat_list(&smaller); // restaurar listas ordenadas
  list.append(pivot);
  list.concat_list(&bigger);
}  

Una lista con un solo elemento o vacía se considera ordenada. Esta es la base del algoritmo recursivo. Luego, el procedimiento declara dos listas: bigger y smaller, y un puntero a un nodo llamado pivot.

El método efectúa un proceso especial de partición (//particionar lista). Grosso modo, después de particionar la lista encontramos un elemento especial, llamado pivote, tal que los elementos de la lista original quedan distribuidos de la siguiente manera:

           smaller       pivot        bigger

smaller está desordenada, pero todos sus elementos son menores que pivot. Simétricamente, bigger también está desordenada, pero todos sus elementos son mayores o iguales que pivot. La lista original list deviene vacía.

La “magía” quicksort reside en que luego del proceso de partición el elemento pivot queda en su posición de ordenamiento definitiva. Así, podemos ordenar las listas smaller y bigger por separado, en nuestro caso por el mismo quicksort, y, al final, tenemos:

  smaller-ordenada      pivot        bigger-ordenada

Lo que al concatenarse depara en la lista completamente ordenada.

2  El proceso de partición

El proceso se instrumenta mediante la siguiente rutina:

    Dnode<int> * 
partition(Dnode<int> & list, Dnode<int> & l, Dnode<int> & r)
{
  Dnode<int> * pivot = list.remove_first();
  while (not list.is_empty())
    {
      Dnode<int> * p = list.remove_first();
      if (DATA(p) < DATA(pivot))
        l.append(p);
      else
        r.append(p);
    }
  return pivot;
} 

La rutina parte la lista list en dos listas; l contiene los elementos menores elementos que el pivote y r los mayores o iguales. El valor de retorno es el pivote mismo.

El principio es sorprendentemente simple -luego de que ha sido revelado-. Primero escogemos como pivote al primer elemento. Luego, eliminado de uno en uno los elementos de list. Los elementos menores que el pivote los colocamos en l, los mayores o iguales en r. Simple! n’est-ce pas? ...

3  Quicksort sin recursión

Imaginemos que ordenamos barajas. Al tener dos particiones y el pivote debemos memorizar una partición y el pivote antes de proceder a ordenar la otra partición. Por ejemplo, memorizamos l y el pivote y procedemos a ordenar r. Cuando r esté lista, entonces recordamos a l y el pivote, ordenamos l y finalmente concatenamos. Si se tratase de una sola partición a memorizar no habría problema, pero puesto que debemos proseguir “particionando” debemos memorizar muchas veces. Para ello usamos una pila, o sea, recordamos lo más fresco, lo último que hemos visto.

Ahh, pero debemos resolver dos problemas. El primero es que el pivote queda “colgando” por ahí. Así que cuando empilemos una partición le atamos su pivote; es como si se colocase el medio mazo de cartas en un pote y la carta pivote se marca con algo de manera que no se nos confunda entre las cartas de la partición.

El segundo problema se relaciona con la posibilidad de que saquemos de la pila un mazo que ya está ordenado. ¿cómo saber que está ordenado sin revisar la partición? Respuesta: cuando metamos en la pila una partición ordenada la marcamos como tal de modo que al sacar una partición sepamos si está ordenada observando la marca.

Así, lo que metemos en la pila es una partición definida así:

struct Partition
{
  Dnode<int> l;        // cabecera de lista
  Dnode<int> * pivot;  // pivot resultante de una partición
  bool sorted;         // true si l está completamente ordenada
...
}; 

Esto es exactamente lo que dijimos que íbamos a meter en la pila: la partición (la lista l), el pivote atado (pivot) y la marca de ordenamiento (sorted).

3.1  ¿Cómo saber cuándo una partición esté ordenada?

Hay dos momentos generales en que podemos concluir que una partición está ordenada: (1) cuando obtenemos una partición de un sólo elemento o vacía y (2) cuando concatenemos dos particiones ya ordenadas.

El caso (1) lo verificamos cuando metamos una partición en la pila. Para ello, empleamos la siguiente rutina:

void push(ArrayStack<Partition> & stack, Dnode<int> & l, 
   Dnode<int> * pivot, bool sort)
{
  if (l.is_empty())
    if (pivot == NULL) 
      return; // partición vacía ==> no se empila
    else
      {   // partición ordenada de un sólo elemento (pivote)
        l.append(pivot);
        stack.push(Partition(l, NULL, true));
        return;
      }

  if (l.is_unitarian())
    {  // partición junto con pivote conforman lista ordenada
      if (pivot != NULL) // ¿hay pivote?
        if (DATA(pivot) <= DATA(l.get_first()))
          l.insert(pivot); 
        else
          l.append(pivot); 

      stack.push(Partition(l, NULL, true));
      return;
    }

  stack.push(Partition(l, pivot, sort));
}

La primitiva toma como parámetros la pila, la lista partición l, el pivote y la marca de ordenamiento.

A través de la sobrecarga (overloading), definimos los siguiente “sabores” de empilamiento:

    // mete en pila lista l y pivot con pivot mayor que l
void push(ArrayStack<Partition> & stack, Dnode<int> & l, 
          Dnode<int> * pivot)
{
  push(stack, l, pivot, false);
}

    // mete en pila pivot y l con pivot menor que l
void push(ArrayStack<Partition> & stack, Dnode<int> * pivot, 
          Dnode<int> & l)
   
{
  push(stack, l, pivot, false);
}

void push(ArrayStack<Partition> & stack, const Partition & part)
{
  stack.push(part);
} 

La idea de estas sobrecargas es facilitar la escritura del programa principal; se empila la partición según el orden el orden de los parámetros.

El segundo momento (2) del cual hablábamos al inicio de esta sección es cuando combinamos dos listas ordenadas en una sola:

Partition combine_partitions(Partition & p1, Partition & p2)
{
  Partition ret_val(p1.l);

  if (DATA(ret_val.l.get_last()) < DATA(p2.l.get_first()))
    ret_val.l.append_list(&p2.l);
  else
    ret_val.l.insert_list(&p2.l);

  return ret_val;
} 

La rutina exige como precondición que p1 y p2 contengan particiones ordenadas y retorna una nueva partición producto de la concatenación de p1 y p2 según sea el orden.

3.2  La versión no recursiva del quicksort

Con todo lo anterior claro, podemos plantear la siguiente versión no recursiva:

void quick_sort(Dnode<int> & list)
{
  ArrayStack<Partition> stack; // la pila
  Dnode<int> l, r;
  Partition part;

  Dnode<int> * pivot = partition(list, l, r); 

  push(stack, l, NULL);
  push(stack, pivot, r);

  while (stack.size() > 1)
    {
      part = pop(stack); 

      if (not part.sorted)
        {   // partición no ordenada ==> particione y empile 
          pivot = partition(part.l, l, r);
          push(stack, l, NULL);
          push(stack, pivot, r);
        }
      else
        {
          Partition part2 = pop(stack); // saca partición contigua
          if (part2.sorted) // si está ordenada podemos combinarlas
            push(stack, combine_partitions(part, part2));
          else
            { // como part2 no está ordenada memorizamos part (que
              // ya está ordenada) y particionamos part2
              push(stack, part); 
              pivot = partition(part2.l, l, r);
              push(stack, l, NULL);
              push(stack, pivot, r);
            }
         } 
    }  

  part = pop(stack);
  list.swap(&part.l);
} 

Hay espacio para mejoras, cuya identificación, discusión y programación se delegan en ejercicios.

Hay un punto delicado que también dejo en ejercicio pero debo comentarlo. Como Dnode<T> es un nodo doble, la asignación y el constructor copia no se realizan, pues no tienen sentido. Su presencia en Aleph-w obedece a razones de compatibilidad y que el gcc es un poco quisquilloso y de vez en cuando los invoca. Esto es importante decirlo para la copia de objetos de tipo Partition, la cual debe invocar al swap y no a la asignación.

4  Conclusión

Como lo mencioné al inicio, este problema se me apareció explicando la eliminación de la recursión.

La recursión es deseable eliminarla en contextos donde la pila del sistema sea escasa. Tal es el caso, por ejemplos, de algunos sistemas embarcados o de procesos con threads, en los cuales la administración de las distintas pilas no sólo es tediosa sino que a menudo los tamaños de pila de la thread pueden ser bastante pequeños (una vez tuve que lidiar con 4Kb).

Sin embargo, resulta que un quicksort bien programado, preparado para el peor caso de consumo de pila no hace más de lgn llevado al entero más alto inserciones en la pila. Si ordenamos 2¹28 elementos, entonces, en el peorsísimo de los casos efectuaremos 128 llamadas recursivas, cantidad soportable por un tamaño de pila pequeño. Por tanto, no valdría mucho la pena la versión no recursiva del quicksort, salvo en un caso excepcionalísimo donde la pila del sistema sea excepcionalmente pequeña.

De todos modos aquí está la rutina. Agradezco, pues las mejoras.

Créditos:

1. La idea de atar el pivote la tuvo Igor cuando en clase colocaba como pivote de una partición que no lo tenía una carta volteada
2. El problema de distinguir si la partición estaba o no ordenada se me apareció luego de un comentario de Stefan sugiriendo que si la partición está ordenada, entonces se podía concatenar el pivote y que no valía la pena “atarlo” a la partición.

---

This document was translated from L^AT_EX by H^EV^EA.