Más sobre ordenamiento de listas enlazadas Leandro Rabindranath León

En el post anterior planteé una versión no recursiva del celebérrimo método de ordenamiento quicksort sobre listas enlazadas. Decía entonces que aquella versión no valía la pena en la inmensa mayoría de casos. Dicho de otro modo, es preferible la versión recursiva.

En este post voy a tratar más sobre ordenamiento de listas enlazadas. Voy a presentar métodos “buenos” y que pueden usarse en código de producción con la seguridad de que han sido probados por aplicaciones de envergadura.

Comencemos revelando una “verdad”: el mejor método de ordenamiento conocido es el quicksort. Del mismo modo, es preferible su versión recursiva a la no recursiva. Ahora bien, el quicksort tiene competidores, así como bastante espacio para la mejora. Por tanto, para estudiar bien el quicksort y saber por qué es “mejor”, es menester entender a sus competidores, de manera que podamos compararlos. Pero también, como las mejoras al quicksort se valen de otros métodos de ordenamiento, es importante entender aquellos métodos y así un quicksort de alto desempeño.

De nuevo, todos los ejemplos se dan en Aleph-w.

Contents

• 1  El quicksort simple
• 2  El método de inserción
• 3  El mergesort
  • 3.1  División de la lista
  • 3.2  Mezcla
  • 3.3  Análisis del mergesort
• 4  Optimización del quicksort
  • 4.1  Consumo de pila
  • 4.2  Selección del pivote
  • 4.3  Acelerado del quicksort con otros métodos de ordenamiento
  • 4.4  Claves repetidas
  • 4.5  Versión final mejorada

1  El quicksort simple

El punto de partida es el quicksort recursivo más simple, el cual se define del siguiente modo:

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

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

  // particionar lista

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

  // concatenar smaller, pivot y bigger
} 

Es tan simple el algoritmo para lo tanto y bien que lo hace, que uno recuerda aquel dicho de “ser demasiado bueno para ser verdad”.

Particionamos list en dos listas smaller y bigger según un elemento llamado pivot (o pivote). Después de // particionar lista, smaller contiene elementos menores que pivot, mientras que bigger los mayores o iguales.

Una vez particionada list, el resto del trabajo es ordenar de nuevo smaller y bigger y luego concatenarlas para obtener list definitivamente ordenada.

Como decíamos en el post pasado, el proceso de partición es harto sencillo -una vez conocido-:

// particionar lista
while (not list.is_empty()) 
{
  Dlink * p = list.remove_first();
  if (Compare () (p, pivot)) // ¿p < pivot?
    smaller.append(p);
  else
    bigger.append(p);
}

Básicamente, sacamos uno a uno cada elemento de list ; si el elemento es menor que pivot, entonces lo añadimos a smaller, de lo contrario, lo añadimos a bigger.

Concatenar smaller, pivot y bigger se hace así:

// concatenar smaller, pivot y bigger
list.concat_list(&smaller); // restaurar listas ordenadas en list
list.append(pivot);
list.concat_list(&bigger);

Aquí nos valemos de la rutina concal_list() implantada en Aleph-w.

Si la partición es equitativa, o sea, los tamaños de l y r se aproximan entre si, entonces el desempeño del quicksort se define mediante la recurrencia T(n) = 2T(n/2) + O(n), la cual es O(n lgn). Pero si la partición no es equitativa, caso extremo, una es vacía y la otra los restantes n−1 elementos, entonces el desempeño se define por la recurrencia T(n) = T(n−1) + O(n), la cual es O(n²). En este caso, el quicksort es el “lento” o “slowsort”, y huelga decir que es más lento que otros métodos cuadráticos.

2  El método de inserción

El método de inserción lo emplean algunos de jugadores de barajas. La idea es tener una lista auxiliar en la cual se insertan ordenadamente las cartas que vamos sacando de list. EL método se implementa muy fácilmente así:

    template <class Compare> 
inline void insertion_sort(Dlink & list)
{
  Dlink aux;

  while (not list.is_empty())
    insert_sorted <Compare> (aux, list.remove_first());

  list.swap(&aux);
}
 

aux es la lista auxiliar.

La inserción ordenada general en una lista la efectúa la rutina insert_sorted(), la cual se implementa así:

    template <class Compare> 
inline void insert_sorted(Dlink & list, Dlink * p)
{
  typename Dlink::Iterator it(list); // buscar primer nodo mayor o igual a p
  while (it.has_curr() and Compare () (it.get_curr(), p)) 
    it.next();

  if (it.has_curr()) 
    it.get_curr()->insert_prev(p); // insertar antes de curr
  else
    list.append(p); 
}
 

Al salir del while, it.get_curr() apunta al primer elemento de list cuyo contenido es mayor o igual a p. Consecuentemente, p va antes de it.get_curr(), lo cual se corresponde con la llamada insert_prev().

El while de insertion_sort() repite exactamente O(n) veces. Por tanto, el desempeño total depende del desempeño de insert_sorted(), el cual a su vez depende de la cantidad de repeticiones del while interno de insert_sorted(). Esta cantidad es bastante relativa, pues depende del valor del elemento p respecto a la secuencia ordenada aux. El peor caso ocurre cuando p es mayor que toda aux, en cuyo caso se recorre enteramente a aux y el método de inserción es O(n²). Si por el contrario p es menor que toda aux, entonces no se repite y el método es O(n). Si la posición de p dentro de aux se considera aleatorias, cual es el caso si la permutación a ordenar es aleatoria, entonces lo esperado es que p, se ponga en el medio de aux, lo que también arroja O(n²) para el método, aunque con la mitad de las repeticiones.

Hay dos observaciones esenciales para el método de inserción:

1. El método tiende a O(n) cuando la permutación está semiordenada.
2. A pesar de ser cuadrático, el método de inserción tiene, por decirlo de una forma, poco coste constante. Es decir, el método tiene pocas operaciones comparado con otros métodos. Esto puede constatarse mediante su simplicidad y pocas líneas de código.

Una posible mejora al método de inserción, la cual aumenta un poco su coste constante, consiste en observar los dos extremos de aux. insert_sorted() sólo observa el extremos izquierdo y no itera si p es menor. Observando el extremo derecho, podemos verificar si p es mayor que toda aux, en cuyo caso lo insertamos al final sin necesidad de buscar en aux su lugar de inserción.

3  El mergesort

Con listas enlazadas, en competidor más importante al quicksort es el mergesort, del cual puede decirse que es tan o más simple que el quicksort:

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

  Dlink l, r;
  list.split_list(l, r);              // dividir en dos listas

  mergesort <Compare> (l);            // ordenar la primera
  mergesort <Compare> (r);            // ordenar la segunda

  merge_lists <Compare> (l, r, list); // mezclarlas 
}

El mergesort() también es un algoritmo dividir combinar y es conceptualmente más simple que el quicksort.

El primer paso consiste en dividir la lista en dos partes equitativas; esto es efectuado por el método split_list() de la clase Dlink. A la gran diferencia del quicksort, split_list() garantiza que l y r tienen tamaños equitativos.

Una vez dividida la lista, se procede a ordenar recursivamente.

Finalmente, con l y r ordenados, se procede a mezclarlas para conformar una sola lista ordenada.

3.1  División de la lista

Hay varia maneras con sus variantes de dividir una lista enlazada en dos partes equitativas. La más simple y en mi opinión más eficiente, permisible con listas dobles, es la siguiente:

// División de lista en dos
void split_list(Dlink & l, Dlink & r) 
{
  while (not is_empty())
    {
      l.append(remove_first()); 

      if (is_empty())
 break;

      r.insert(remove_last());
    }
}
 

Es decir, sacamos el primer elemento y lo insertamos al final de l. Luego sacamos el último elemento y lo metemos al principio de r. Continuamos este proceso hasta que hayamos eliminado todos los elementos de this (split_list() es un método de la clase Dlink). Al final, l contiene los n/2 primeros elementos de this y r los n/2 siguientes.

En el interés del ordenamiento, la gran diferencia entre split_list() y el bloque // particionar lista es que éste último mueve elementos de las lista y los acerca a su posición definitiva de ordenamiento. Contrariamente, split_list() los deja tal cual. A pesar de que // particionar lista no garantiza que las particiones sean equitativas, éste hace trabajo en pos del ordenamiento definitivo, trabajo que luego recompensará con creces la inversión en los intercambios.

split_list es O(n), con mucho menor coste constante que // particionar lista, pero también con mucho menos trabajo útil para el ordenamiento.

Nuestra implementación de split_list() sólo es válida para listas dobles. Para listas simples, empleamos dos punteros p y q, inicializados sobre el primer elemento. Recorremos la lista hasta llegar al final, avanzando un puntero normalmente y el otro al doble de velocidad (de dos en dos). Cuando el puntero más rápido alcance el final de la lista, el más lento se encuentra a la mitad, cual es el punto de corte deseado.

split_list() consume O(n).

3.2  Mezcla

La parte de combinar (o conquista) del mergesort es la propia mezcla (merge), la cual se instrumenta así:

    template <class Compare> inline
void merge_lists(Dlink & l1, Dlink & l2, Dlink & result)
{
  while (not l1.is_empty() and not l2.is_empty())
    if (Compare () (l1.get_first(), l2.get_first()))
      result.append(l1.remove_first());
    else
      result.append(l2.remove_first());

  if (l1.is_empty())
    result.concat_list(&l2);
  else
    result.concat_list(&l1);
}

La entrada son las listas ordenadas l1 y l2 ; la salida es una sola lista ordenada llamada result.

Observamos los primeros elementos de l1 y l2, escogemos el menor de ellos, lo eliminamos de su lista y lo insertamos al final de result. Repetimos hasta que una l1 o l2 esté vacía. Al terminar el proceso, result está completamente ordenada y la lista no vacía que queda, que está ordenada, contiene elementos mayores que todos los de result ; así que los concatenamos al final de result y obtenemos el orden definitivo.

La mezcla revisa todos los elementos, lo cual es O(n).

3.3  Análisis del mergesort

Podemos definir el tiempo de ejecución del mergesort del siguiente modo:

T(n) = O(n) + 2 T(n/2) + O(n)

El cual es O(n lgn). No obstante, la recurrencia nos muestra una diferencia de desempeño muy importante respecto al quicksort: el coste O(n) correspondiente a la mezcla. Dicho de otro modo, el quicksort consume una sola pasada sobre la lista; el mergesort dos.

4  Optimización del quicksort

Ahora vamos progresivamente a mejorar el quicksort.

4.1  Consumo de pila

La instrumentación de una llamada procedimiento se vale de una pila especial, manejada en cooperación por el procesador, el sistema operativo y el compilador y que se denomina “pila sistema”. Grosso modo, para recordar el lugar de regreso al llamar a un procedimiento, se empila este lugar ene la pila sistema. De este modo, al terminar el procedimiento, se desempila la dirección de regreso.

Cuantas más llamadas anidadas haga un procedimiento mayor será el consumo de la pila sistema. En el caso de un procedimiento recursivo, es obvio que ocurrirán muchos más empilamientos; consecuentemente, el consumo de la pila sistema será mayor. Así, cuando se diseña un procedimiento recursivo, se debe calcular la cantidad máxima de llamadas recursivas, pues la pila sistema es bastante limitada en tamaño (típicamente unos 64 Kb)

En el caso de quicksort la cantidad de recursiones depende de la cantidad de veces que se particione. A su vez, esta cantidad depende de la suerte en donde caiga el pivote. Así, si el pivote cae por el centro y así sucesivamente, entonces a lo sumo se recursiona ⌊ lg n⌋ veces. Pero si el pivote siempre cae por el extremo, entonces se recursiona anidadamente n veces, lo que revienta cualquier pila sistema, inclusive para tamaños de listas relativamente pequeños.

La manera de evitar el problema anterior es asegurarse de recursionar de primero sobre la partición más pequeña. Si logramos esto, es decir, que siempre se ordene de primero la partición más pequeña y luego la más grande, entonces la máxima cantidad de veces que se puede recursionar es ⌊logn⌋.

Para poder decidir cuál entre las dos particiones es la más pequeña, debemos conocer sus longitudes, lo cual no es un conocimiento directo, pues, en aras de preservar su dinamismo, no es conveniente manejar la cardinalidad de una lista enlazada. Sin embargo, el quicksort tiene una oportunidad, que no debemos desperdiciar, para contabilizar cardinalidades: el proceso de partición. Así, planteamos la siguiente modificación a la partición:

// particionar lista y contar
Dlink smaller, bigger; 
size_t smaller_sz = 0, bigger_sz = 0;
while (not list.is_empty()) 
{
  Dlink * p = list.remove_first();
  if (Compare () (p, pivot)) // ¿p < pivot?
    { smaller.append(p); ++smaller_sz; }
  else
    { bigger.append(p); ++bigger_sz; }
}

Al terminar de particionar, smaller_sz y bigger_sz contienen las cardinalidades de smaller y bigger respectivamente.

Conocidas las cardinalidades, la versión mejorada del quicksort se define del siguiente modo:

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

  Dlink * pivot = list.remove_first();

  // particionar lista y contar

  if (smaller_sz < bigger_sz)
    {
      quicksort <Compare> (smaller);
      quicksort <Compare> (bigger);  
    }
  else
    {
      quicksort <Compare> (bigger);  
      quicksort <Compare> (smaller);
    }

  // concatenar smaller, pivot y bigger
} 

4.2  Selección del pivote

Consideremos el caso improbable, aunque posible, de que la lista esté inversamente desordenada. Con esa entrada, nuestro quicksort siempre particiona así: {partición inversamente ordenada}-pivot-∅, lo que acarrea un coste de O(n²). Si bien este caso improbable (2/n!), hay más probabilidades de obtener malas particiones que las dos peores. Dicho de otro modo, no es bueno tener malas particiones, razón por la cual vale la pena invertir un poco de trabajo constante en mitigar la posibilidad de obtener un mal pivote.

Una primera táctica es escoger el pivote al azar y no de una de las puntas de la lista como en nuestro caso. Sin embargo, esta técnica tiene dos problemitas, uno de instrumentación y otro con la suerte.

La idea del azar es tirar un número aleatorio acotado a la cardinalidad de la lista y luego escoger como pivote el elemento en la posición ordinal. Con arreglos esto es directo, pero con listas no, pues no conocemos a priori la cardinalidad y el acceso por posición no es directo. Lo de la cardinalidad no es tanto problema, pues a partir de la primera partición ya la conoceríamos. Podríamos modificar el quicksort para que reciba de parámetros la cardinalidad previamente contada en la partición anterior.

El acceso a la posición generada al azar acarrea una penalidad severa, pues requiere recorrer la lista (con arreglos no existe este problema). Sin embargo, comparado al mergesort, vale la pena observar que el recorrido será menor la inmensa mayoría de veces y que luego la partición aportará más trabajo útil.

Escoger un solo pivote al azar combate una mala partición causada por una mala permutación (una semi ordenada, por ejemplo), pero no combate la mala suerte misma. El elemento escogido al azar podría ser un mal pivote. Por ello, para mitigar este problema se pueden mirar varios elementos al azar y escoger como pivote la mediana.

En esta sección nos ahorraremos el recorrido mirando 3 elementos extremos de la lista y seleccionando la mediana. El azar lo introduciremos un poco seleccionando al azar en cuál extremo de la lista miraremos el tercer elemento. Así las cosas, la selección del pivote se realiza mediante la siguiente rutina:

    template <class Compare>
Dlink * select_pivot(Dlink & list) 
{
  Dnode<T> * first  = list.get_first();
  Dnode<T> * last = list.get_last();
  Dnode<T> * third = NULL;
  long r = // generar un número aleatorio o pseudoaleatorio
  if (r % 2 == 0) // ¿es par?
    r = first->get_next();
  else
    r = last->get_prev();

  Dnode<T> * pmax, * pmin;
  if (Compare () (first, last))
    { pmin = first; pmax = last; }
  else
    { pmin = last; pmax = first; }

  if (Compare () (third, pmin))
    pmin = third;

  if (Compare () (pmax, third))
    pmax = third;

  Dnode<T> * pivot;
  if (first != pmin and first != pmax)
    pivot = first;
  else if (last != pmin and last != pmax)
    pivot = last;
  else
    pivot = third;

  pivot->del();

  return pivot;
}

La rutina escoge el pivote según el criterio explicado, lo elimina de la lista y lo retorna.

Para que tenga sentido escoger la mediana de tres elementos la lista debe contener tres o más elementos; pero esta validación no será necesaria a la luz de otra mejora que presentaremos prontamente.

4.3  Acelerado del quicksort con otros métodos de ordenamiento

Observaciones empíricas han revelado que otros métodos de ordenamiento cuadráticos, notablemente el de inserción, exhiben mejor rendimiento que el quicksort cuando se emplean para particiones pequeñas. La escala de lo pequeño es variable según el tipo de dato y hardware. Por eso, emplearemos la siguiente variable global ajustable:

size_t quicksort_threshold = 1000;

Cuando el tamaño de una partición sea menor o igual a quicksort_threshold, entonces ordenaremos mediante el método de inserción.

A modo de ilustración, planteamos la siguiente versión mejorada, aunque incompleta -sin las otras mejoras-:

    template <class Compare> 
void quicksort(Dlink & list, const size_t list_sz = quicksort_threshold + 1) 
{
  if (list_sz <= quicksort_threshold)
    {
      insertion_sort <Compare> (list);
      return;
    }

  Dlink * pivot = select_pivot(list);

  // particionar lista y contar

  quicksort <Compare> (bigger, bigger_sz);  
  quicksort <Compare> (smaller, smaller_sz);
}

La rutina recibe de parámetros la lista list que se desea ordenar y su tamaño list_sz. La idea es muy sencilla: si el tamaño de la partición es menor o igual que quicksort_threshold, entonces ordenamos por el método de inserción, el cual se esperaría fuese más veloz que el mero quicksort. Nótese que ya no es necesario verificar la condición de parada recursiva; ésta fue sustituida por el if.

Hay un “truquito” o ardid que bien vale la pena mencionar: el uso de un valor por omisión par el parámetro list_sz. Con este truquito, la presentación oficial del quicksort y la llamada inicial son idénticas a las versiones previas. Puesto que el valor por omisión es mayor que quicksort_threshold es seguro que la primera llamada invocará al quicksort, lo cual no es grave pue sno conocemos la longitud inicial de la lista. Así, la primera llamada calculará las particiones iniciales junto con sus tamaños y a partir de allí trabajará con valores correctos de las cardinalidades.

Hay una pequeña debilidad del truquito: no funciona correctamente si la lista inicial tiene dos o menos elementos (puede fallar cuando se llame a select_pivot()). Colocar una verificación para este caso particular e improbables es fastidioso, pues se paga en desempeño por algo muy particular. Por esa razón, especificamos como parte del contrato que la lista a ordenar debe tener tres o más elementos.

4.4  Claves repetidas

Durante la partición se puede reducir la cantidad total de elementos a ordenar si agrupamos los que son iguales al pivote en una tercera lista. De este modo, refinamos la partición de la siguiente manera:

// partición con claves repetidas
Dlink smaller, bigger, equal; 
size_t smaller_sz = 0, bigger_sz = 0;
while (not list.is_empty()) 
{
  Dlink * p = list.remove_first();
  if (Compare () (p, pivot)) // ¿p < pivot?
    { smaller.append(p); ++smaller_sz; }
  else if (Compare () (pivot, p)) // ¿pivot < p?
    { bigger.append(p); ++bigger_sz; }
  else
    equal.append(p); 
}

Esta técnica es denominada “partición a la bandera holandesa”, en honor a la nacionalidad de Dijkstra, su primer descubridor conocido.

Por supuesto, si se reduce la cantidad de elementos a ordenar, entonces se reduce el tiempo de ordenamiento. El coste constante es de solo una comparación.

La tercera lista la llamamos equal y nos fuerza a modificar // concatenar smaller, pivot y bigger para que opere sobre las tres listas:

// concatenar smaller, equal y bigger
list.concat_list(&smaller); // restaurar listas ordenadas en list
list.append(&equal);
list.concat_list(&bigger);

4.5  Versión final mejorada

La técnicas anteriores las podemos comulgar en la siguiente versión:

    template <class Compare> 
void quicksort(Dlink & list, const size_t list_sz = quicksort_threshold) 
{
 if (list_sz <= quicksort_threshold)
    {
      insertion_sort <Compare> (list);
      return;
    }

  Dlink * pivot = select_pivot(list);

  // particionar lista con claves repetidas

  if (smaller_sz < bigger_sz)
    {
      quicksort <Compare> (smaller);
      quicksort <Compare> (bigger);  
    }
  else
    {
      quicksort <Compare> (bigger);  
      quicksort <Compare> (smaller);
    }

  // concatenar smaller, equal y bigger
} 

---

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

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.