¿Cómo implementar algoritmos de ordenación clásicos en C++moderno?

Bloques de construcción algorítmicos

Comenzamos ensamblando los bloques de construcción algorítmicos de la Biblioteca Estándar: {[116]]}

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next

• las herramientas iteradoras como non-member std::begin() / std::end() así como con std::next() solo están disponibles a partir de C++11 y más allá. Para C++98, uno necesita escribirlos él mismo. Hay sustitutos de Boost.Rango en boost::begin() / boost::end(), y de Boost.Utilidad en boost::next().
• el algoritmo std::is_sorted solo está disponible para C++11 y más allá. Para C++98, esto se puede implementar en términos de std::adjacent_find y un objeto de función escrito a mano. Impulsar.El algoritmo también proporciona un boost::algorithm::is_sorted como sustituto.
• el algoritmo std::is_heap solo está disponible para C++11 y más allá.

Golosinas sintácticas

C++14 proporciona comparadores transparentes de la forma std::less<> que actúan polimórficamente sobre sus argumentos. Esto evita tener que proporcionar un tipo de iterador. Esto se puede utilizar en combinación con C++11's argumentos de plantilla de función predeterminados para crear una única sobrecarga para los algoritmos de ordenación que toman < como comparación y aquellos que tienen un objeto de función de comparación definido por el usuario.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

En C++11, se puede definir un alias de plantilla para extraer el tipo de valor de un iterador que agrega un desorden menor a las firmas de los algoritmos de ordenación:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

En C++98, uno necesita escribir dos sobrecargas y utilice la sintaxis detallada typename xxx<yyy>::type

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}

• Otra sutileza sintáctica es que C++14 facilita la envoltura de comparadores definidos por el usuario a través de lambdas polimórficas (con auto parámetros que se deducen como argumentos de plantilla de función).
• C++11 solo tiene lambdas monomórficas, que requieren el uso del alias de la plantilla anterior value_type_t.
• En C++98, uno necesita escribir un objeto de función independiente o recurrir a la verbosa std::bind1st / std::bind2nd / std::not1 tipo de sintaxis.
• Aumentar.Bind mejora esto con boost::bind y _1 / _2 sintaxis de marcador de posición.
• C++11 y más allá también tienen std::find_if_not, mientras que C++98 necesita std::find_if con un std::not1 alrededor de un objeto de función.

Estilo C++

Todavía no hay un estilo C++14 generalmente aceptable. Para bien o para mal, sigo de cerca a Scott Meyers proyecto Efectivo Moderno C++ y Herb Sutter's renovado GotW. Utilizo las siguientes recomendaciones de estilo:

• Herb Sutter's "Casi Siempre Auto" y Scott Meyers "Prefiera auto a declaraciones de tipo específicas" recomendación, para la que la brevedad es insuperable, aunque su claridad es a veces impugnada.
• Scott Meyers "Distinguir () y {} al crear objetos" y consistentemente elija la inicialización entre corchetes {} en lugar de la buena inicialización entre paréntesis () (para evitar todos los problemas de análisis más molestos en el código genérico).
• Scott Meyers "Preferir las declaraciones de alias a typedefs". Para las plantillas esto es una necesidad de todos modos, y usarlo en todas partes en lugar de typedef ahorra tiempo y agrega consistencia.
• Utilizo un patrón for (auto it = first; it != last; ++it) en algunos lugares, con el fin de permitir la comprobación invariante de bucle para ya ordenados sub-rangos. En código de producción, el uso de while (first != last) y un ++first en algún lugar dentro del bucle podría ser ligeramente mejor.

Selección ordenar

Selección ordenar no se adapta a los datos de ninguna manera, por lo que su tiempo de ejecución es siempre O(N²). Sin embargo, selection sort tiene la propiedad de minimizando el número de swaps. En aplicaciones donde el costo de intercambiar elementos es alto, selection sort muy bien puede ser el algoritmo de elección.

A implementarlo usando la Biblioteca Estándar, usar repetidamente std::min_element para encontrar el elemento mínimo restante, y iter_swap para cambiarlo en su lugar:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Tenga en cuenta que selection_sort tiene el rango ya procesado [first, it) ordenado como su invariante de bucle. Los requisitos mínimos son iteradores forward, en comparación con los iteradores de acceso aleatorio de std::sort.

Detalles omitidos :

• la clasificación de selección se puede optimizar con una prueba temprana if (std::distance(first, last) <= 1) return; (o para adelante / iteradores bidireccionales: if (first == last || std::next(first) == last) return;).
• para iteradores bidireccionales, la prueba anterior se puede combinar con un bucle sobre el intervalo [first, std::prev(last)), porque se garantiza que el último elemento es el elemento restante mínimo y no requiere un intercambio.

Ordenación por inserción

Aunque es uno de los algoritmos de ordenación elementales con O(N²) el tiempo en el peor de los casos, ordenar por inserción es el algoritmo de elección, ya sea cuando los datos es casi ordenado (porque es adaptable) o cuando el tamaño del problema es pequeño (porque tiene una sobrecarga baja). Por estas razones, y porque también es estable, la ordenación por inserción se usa a menudo como el caso base recursivo (cuando el tamaño del problema es pequeño) para algoritmos de ordenación de división y conquista más altos, como la ordenación combinada o la ordenación rápida.

Para implementar insertion_sort con la Biblioteca Estándar, utilice repetidamente std::upper_bound para encontrar la ubicación donde el elemento actual necesita ir, y usar std::rotate para desplazar los elementos restantes hacia arriba en el rango de entrada:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Tenga en cuenta que insertion_sort tiene el rango ya procesado [first, it) ordenado como su invariante de bucle. La ordenación por inserción también funciona con iteradores hacia adelante.

Detalles omitidos :

• la ordenación por inserción se puede optimizar con una prueba temprana if (std::distance(first, last) <= 1) return; (o para iteradores hacia adelante / bidireccionales: if (first == last || std::next(first) == last) return;) y un bucle sobre el intervalo [std::next(first), last), porque el primer elemento es garantizado para estar en su lugar y no requiere una rotación.
• para los iteradores bidireccionales, la búsqueda binaria para encontrar el punto de inserción se puede reemplazar con una búsqueda lineal inversa utilizando el algoritmo std::find_if_not de la biblioteca Estándar.

Cuatro Ejemplos en Vivo (C++14, C++11, C++98 y Boost, C++98) el fragmento de abajo:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();

• Para entradas aleatorias esto da O(N²) comparaciones, pero esto mejora a O(N) comparaciones para entradas casi ordenadas. La búsqueda binaria siempre usa comparaciones O(N log N).
• Para rangos de entrada pequeños, la mejor localidad de memoria (caché, prefetching) de una búsqueda lineal también podría dominar una búsqueda binaria (uno debería probar esto, por supuesto).

Ordenación rápida

Cuando se aplica cuidadosamente, clasificación rápida es robusto y tiene O(N log N) complejidad esperada, pero con O(N²) complejidad en el peor de los casos que puede activarse con datos de entrada elegidos adversariamente. Cuando no se necesita una clasificación estable, la clasificación rápida es una excelente clasificación de propósito general.

Incluso para las versiones más simples, quick sort es bastante más complicado de implementar usando la Biblioteca Estándar que los otros algoritmos de ordenación clásicos. El enfoque a continuación utiliza algunas utilidades iteradoras para localizar el elemento medio del rango de entrada [first, last) como pivote, luego use dos llamadas a std::partition (que son O(N)) para dividir el rango de entrada en segmentos de elementos que son más pequeños, iguales y mayores que el pivote seleccionado, respectivamente. Finalmente, los dos segmentos exteriores con elementos más pequeños y más grandes que el pivote se ordenan recursivamente:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

Sin embargo, la clasificación rápida es bastante difícil de obtener correcta y eficiente, ya que cada uno de los pasos anteriores debe revisarse cuidadosamente y optimizarse para código de nivel de producción. En particular, para la complejidad O(N log N), el pivote tiene que resultar en una partición equilibrada de los datos de entrada, que no se puede garantizar en general para un pivote O(1), pero que se puede garantizar si se establece el pivote como la mediana O(N) del rango de entrada.

Detalles omitidos :

• la implementación anterior es particularmente vulnerable a entradas especiales, por ejemplo, tiene O(N^2) complejidad para la entrada" tubo de órgano " 1, 2, 3, ..., N/2, ... 3, 2, 1 (porque el centro es siempre más grande que todos los demás elementos).
• mediana-de-3 selección de pivote desde elementos elegidos al azar from the input range protege contra entradas casi clasificadas para las que la complejidad se deterioraría de otro modo a O(N^2).
• 3-forma de partición (separando elementos más pequeños que, iguales y más grandes que el pivote) como se muestra en las dos llamadas a std::partition no es el más algoritmo O(N) eficiente para lograr este resultado.
• para iteradores de acceso aleatorio, una complejidad garantizada O(N log N) se puede lograr a través de selección de pivote mediano utilizando std::nth_element(first, middle, last), seguido de llamadas recursivas a quick_sort(first, middle, cmp) y quick_sort(middle, last, cmp).
• esta garantía tiene un costo, sin embargo, porque el factor constante de la complejidad O(N) de std::nth_element puede ser más caro que el de la complejidad O(1) de un pivote de mediana de 3 seguido de una llamada O(N) a std::partition (que es un simple paso hacia adelante amigable con la caché sobre los datos).

Merge sort

Si usar O(N) espacio adicional no es de ninguna preocupación, entonces combinar ordenar es una excelente opción: es el único estable O(N log N) algoritmo de ordenación.

Es fácil de implementar usando algoritmos estándar: use algunas utilidades iteradoras para localizar el medio del rango de entrada [first, last) y combine dos segmentos ordenados recursivamente con un std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Merge sort requiere iteradores bidireccionales, siendo el cuello de botella std::inplace_merge. Tenga en cuenta que al ordenar listas vinculadas, la ordenación combinada solo requiere O(log N) espacio adicional (para la recursión). Este último algoritmo es implementado por std::list<T>::sort en la Biblioteca Estándar.

Tipo de pila

Ordenar por montón es fácil de implementar, realiza una ordenación in situ O(N log N), pero no es estable.

El primer bucle, O(N) fase "heapify", pone la matriz en orden de pila. El segundo bucle, la fase "sortdown" O(N log N), extrae repetidamente el máximo y restaura el orden del montón. La Biblioteca Estándar hace esto extremadamente sencillo:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

En caso de que consideres "engaño" usar std::make_heap y std::sort_heap, puedes ir un nivel más profundo y escribir esas funciones tú mismo en términos de std::push_heap y std::pop_heap, respectivamente:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

La Biblioteca Estándar especifica push_heap y pop_heap como complejidad O(log N). Tenga en cuenta, sin embargo, que la el bucle externo sobre el rango [first, last) resulta en O(N log N) complejidad para make_heap, mientras que std::make_heap solo tiene O(N) complejidad. Para la complejidad general O(N log N) de heap_sort no importa.

Los Detalles omitidos: O(N) la aplicación de make_heap

Pruebas

Aquí hay cuatro Ejemplos en Vivo (C++14, C++11, C++98 y Aumentar, C++98) probando los cinco algoritmos en una variedad de entradas (no pretende ser exhaustiva o rigurosa). Solo tenga en cuenta las enormes diferencias en la LOC: C++11/C++14 necesitan alrededor de 130 LOC, C++98 y Boost 190 (+50%) y C++98 más de 270 (+100%).