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.