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

El std::sortalgoritmo (y sus primos std::partial_sorty std::nth_element) de la Biblioteca estándar de C ++ es, en la mayoría de las implementaciones, una amalgamación complicada e híbrida de algoritmos de clasificación más elementales , como clasificación de selección, clasificación de inserción, clasificación rápida, clasificación de fusión o clasificación de montón.

Hay muchas preguntas aquí y en sitios hermanos como https://codereview.stackexchange.com/ relacionadas con errores, complejidad y otros aspectos de las implementaciones de estos algoritmos de clasificación clásicos. La mayoría de las implementaciones ofrecidas consisten en bucles sin procesar, usan manipulación de índices y tipos concretos, y generalmente no son triviales para analizar en términos de corrección y eficiencia.

Pregunta : ¿cómo se pueden implementar los algoritmos de clasificación clásicos mencionados anteriormente utilizando C ++ moderno?

• sin bucles sin procesar , pero combinando los bloques de construcción algorítmicos de la Biblioteca Estándar<algorithm>
• interfaz de iterador y uso de plantillas en lugar de manipulación de índices y tipos concretos
• Estilo C ++ 14 , incluida la biblioteca estándar completa, así como reductores de ruido sintáctico, como autoalias de plantillas, comparadores transparentes y lambdas polimórficas.

Notas :

• Para obtener más referencias sobre implementaciones de algoritmos de clasificación, consulte Wikipedia , Rosetta Code o http://www.sorting-algorithms.com/
• De acuerdo con las convenciones de Sean Parent (diapositiva 39), un bucle sin procesar es un forbucle más largo que la composición de dos funciones con un operador. Así que f(g(x));o f(x); g(x);o f(x) + g(x);no son bucles primas, como tampoco lo son los bucles en selection_sorty insertion_sortpor debajo.
• Sigo la terminología de Scott Meyers para denotar el C ++ 1y actual como C ++ 14, y para denotar C ++ 98 y C ++ 03, ambos como C ++ 98, así que no me llame por eso.
• Como se sugiere en los comentarios de @Mehrdad, proporciono cuatro implementaciones como un ejemplo en vivo al final de la respuesta: C ++ 14, C ++ 11, C ++ 98 y Boost y C ++ 98.
• La respuesta en sí se presenta solo en términos de C ++ 14. Cuando sea relevante, denoto las diferencias sintácticas y de biblioteca donde difieren las diferentes versiones de idioma.

Bloques de construcción algorítmicos

Comenzamos ensamblando los bloques de construcción algorítmicos de la Biblioteca estándar:

#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 de iterador, como no miembro std::begin()/ std::end()así como con std::next(), solo están disponibles a partir de C ++ 11 y posteriores. Para C ++ 98, uno necesita escribirlos él mismo. Hay sustitutos de Boost.Range en boost::begin()/ boost::end(), y de Boost.Utility en boost::next().
• el std::is_sortedalgoritmo solo está disponible para C ++ 11 y más allá. Para C ++ 98, esto se puede implementar en términos de std::adjacent_findy un objeto de función escrito a mano. Boost.Algorithm también proporciona a boost::algorithm::is_sortedcomo sustituto.
• el std::is_heapalgoritmo 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 usar en combinación con los argumentos de la plantilla de función predeterminada de C ++ 11 para crear una sola sobrecarga para los algoritmos de clasificación que toman <como comparación y los 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 reutilizable para extraer el tipo de valor de un iterador que agrega un desorden menor a las firmas de los algoritmos de clasificació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 usar la typename xxx<yyy>::typesintaxis detallada

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 característica sintáctica es que C ++ 14 facilita el ajuste de los comparadores definidos por el usuario a través de lambdas polimórficas (con autopará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 plantilla anterior value_type_t.
• En C ++ 98, uno necesita escribir un objeto de función independiente o recurrir al tipo de sintaxis detallado std::bind1st/ std::bind2nd/ std::not1.
• Boost.Bind mejora esto con boost::bindy _1/ _2sintaxis de marcador de posición.
• C ++ 11 y más allá también tienen std::find_if_not, mientras que C ++ 98 necesidades std::find_ifcon una std::not1alrededor de un objeto función.

Estilo C ++

Todavía no existe un estilo C ++ 14 generalmente aceptable. Para bien o para mal, sigo de cerca el borrador de Scott Meyers, Effective Modern C ++, y el renovado GotW de Herb Sutter . Yo uso las siguientes recomendaciones de estilo:

• La recomendación "Casi siempre automática" de Herb Sutter y la recomendación "Prefiera auto a declaraciones de tipo específico " de Scott Meyers , por lo que la brevedad es insuperable, aunque a veces se cuestiona su claridad .
• "Distinguir ()y {}al crear objetos" de Scott Meyers y elegir consistentemente la inicialización {}entre paréntesis ()en lugar de la buena inicialización entre paréntesis (para evitar todos los problemas de análisis más molestos en código genérico).
• Scott Meyers "Prefiere las declaraciones de alias a typedefs" . Para las plantillas, esto es imprescindible de todos modos, y usarlo en todas partes en lugar de typedefahorrar tiempo y agrega consistencia.
• Utilizo un for (auto it = first; it != last; ++it)patrón en algunos lugares, para permitir la comprobación invariante de bucles para subrangos ya ordenados. En el código de producción, el uso de while (first != last)y en ++firstalgún lugar dentro del bucle podría ser un poco mejor.

Tipo de selección

El orden de selección no se adapta a los datos de ninguna manera, por lo que su tiempo de ejecución es siempreO(N²). Sin embargo, la selección por selección tiene la propiedad de minimizar el número de intercambios . En aplicaciones donde el costo de intercambiar elementos es alto, la selección por selección muy bien puede ser el algoritmo de elección.

Para implementarlo usando la Biblioteca estándar, use repetidamente std::min_elementpara encontrar el elemento mínimo restante y iter_swapcambiarlo a 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_sorttiene el rango ya procesado [first, it)ordenado como su bucle invariante. Los requisitos mínimos son iteradores directos , en comparación con std::sortlos iteradores de acceso aleatorio.

Detalles omitidos :

• La ordenación por selección se puede optimizar con una prueba temprana if (std::distance(first, last) <= 1) return;(o para iteradores directos / bidireccionales:) if (first == last || std::next(first) == last) return;.
• Para los iteradores bidireccionales , la prueba anterior se puede combinar con un bucle durante el intervalo [first, std::prev(last)), ya que el último elemento está garantizado como el elemento restante mínimo y no requiere un intercambio.

Tipo de inserción

Aunque es uno de los algoritmos de clasificación elemental con el O(N²)peor de los casos, la clasificación por inserción es el algoritmo de elección cuando los datos están casi ordenados (porque son adaptativos ) o cuando el tamaño del problema es pequeño (porque tiene una sobrecarga baja). Por estas razones, y debido a que también es estable , la ordenación por inserción a menudo se usa como el caso base recursivo (cuando el tamaño del problema es pequeño) para algoritmos de clasificación de divide y vencerás más elevados, como la ordenación por fusión o la ordenación rápida.

Para implementar insertion_sortcon la Biblioteca estándar, use repetidamente std::upper_boundpara encontrar la ubicación donde debe ir el elemento actual y use std::rotatepara 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_sorttiene el rango ya procesado [first, it)ordenado como su bucle invariante. 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 durante el intervalo [std::next(first), last), porque se garantiza que el primer elemento esté 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 std::find_if_notalgoritmo de la Biblioteca estándar .

Cuatro ejemplos en vivo ( C ++ 14 , C ++ 11 , C ++ 98 y Boost , C ++ 98 ) para el siguiente fragmento:

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 proporciona O(N²)comparaciones, pero esto mejora las O(N)comparaciones para entradas casi ordenadas. La búsqueda binaria siempre usa O(N log N)comparaciones.
• Para rangos de entrada pequeños, la mejor localidad de memoria (caché, captación previa) 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 implementa con cuidado, la ordenación rápida es robusta y tiene la O(N log N)complejidad esperada, pero con la O(N²)peor de las situaciones que se puede desencadenar con datos de entrada elegidos de forma contradictoria. Cuando no se necesita una ordenación estable, la ordenación rápida es una excelente ordenación de propósito general.

Incluso para las versiones más simples, la ordenación rápida es bastante más complicada de implementar utilizando la Biblioteca estándar que los otros algoritmos de ordenación clásicos. El siguiente enfoque utiliza algunas utilidades de iterador para ubicar el elemento central del rango de entrada [first, last)como pivote, luego usa dos llamadas a std::partition(que son O(N)) para dividir en tres vías el rango de entrada en segmentos de elementos que son más pequeños, iguales a, y más grande que el pivote seleccionado, respectivamente. Finalmente, los dos segmentos externos 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 ordenación rápida es bastante difícil de obtener de manera correcta y eficiente, ya que cada uno de los pasos anteriores debe verificarse cuidadosamente y optimizarse para el código de nivel de producción. En particular, por O(N log N)complejidad, el pivote tiene que dar como resultado una partición equilibrada de los datos de entrada, que no se puede garantizar en general para un O(1)pivote, pero que se puede garantizar si se establece el pivote como la O(N)mediana 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 de " órgano organ " 1, 2, 3, ..., N/2, ... 3, 2, 1(porque el medio siempre es más grande que todos los demás elementos).
• La selección de pivote de mediana de 3 de elementos elegidos aleatoriamente del rango de entrada protege contra entradas casi ordenadas para las cuales la complejidad se deterioraríaO(N^2).
• La partición de 3 vías (separando elementos más pequeños, iguales y más grandes que el pivote) como lo muestran las dos llamadas astd::partitionno es elO(N)algoritmomás eficientepara lograr este resultado.
• Para los iteradores de acceso aleatorio , O(N log N)se puede lograr una complejidad garantizada mediante la selección de pivote medio usando std::nth_element(first, middle, last), seguido de llamadas recursivas a quick_sort(first, middle, cmp)y quick_sort(middle, last, cmp).
• Sin embargo, esta garantía tiene un costo, porque el factor constante de la O(N)complejidad de std::nth_elementpuede ser más costoso que el de la O(1)complejidad de un pivote de mediana de 3 seguido de una O(N)llamada a std::partition(que es un paso hacia adelante único compatible con caché los datos).

Ordenar fusión

Si el uso de O(N)espacio adicional no es motivo de preocupación, la combinación de clasificación es una excelente opción: es el único algoritmo de clasificación estable O(N log N) .

Es simple de implementar usando algoritmos estándar: use algunas utilidades de iterador para ubicar el medio del rango de entrada [first, last)y combine dos segmentos recursivamente ordenados 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));
}

La ordenación por fusión requiere iteradores bidireccionales, siendo el cuello de botella el std::inplace_merge. Tenga en cuenta que al ordenar las listas vinculadas, la ordenación por fusión solo requiere O(log N)espacio adicional (para la recursividad). El último algoritmo se implementa std::list<T>::sorten la Biblioteca estándar.

Tipo de montón

La ordenación del montón es simple de implementar, realiza unaO(N log N)ordenación in situ, pero no es estable.

El primer ciclo, la O(N)fase "heapify", pone la matriz en orden de montón. El segundo ciclo, la O(N log Nfase de "clasificación", extrae repetidamente el máximo y restaura el orden de almacenamiento dinámico. La Biblioteca estándar hace que esto sea 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 que es "trampa" usar std::make_heapy std::sort_heap, puedes ir un nivel más profundo y escribir esas funciones tú mismo en términos de std::push_heapy 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 ambos push_heapy pop_heapcomo complejidad O(log N). Sin embargo , tenga en cuenta que el bucle externo sobre el rango [first, last)resulta en O(N log N)complejidad para make_heap, mientras que std::make_heapsolo tiene O(N)complejidad. Por la O(N log N)complejidad general de heap_sorteso no importa.

Detalles omitidos : O(N)implementación demake_heap

Pruebas

Aquí hay cuatro ejemplos en vivo ( C ++ 14 , C ++ 11 , C ++ 98 y Boost , C ++ 98 ) que prueban los cinco algoritmos en una variedad de entradas (no pretende ser exhaustivo o riguroso). Solo tenga en cuenta las grandes diferencias en el LOC: C ++ 11 / C ++ 14 necesita alrededor de 130 LOC, C ++ 98 y Boost 190 (+ 50%) y C ++ 98 más de 270 (+ 100%).

Otro pequeño y bastante elegante originalmente encontrado en la revisión de código . Pensé que valía la pena compartirlo.

Tipo de conteo

Si bien es bastante especializado, el ordenamiento de conteo es un algoritmo de ordenación de enteros simple y, a menudo, puede ser realmente rápido siempre que los valores de los enteros para ordenar no estén demasiado separados. Probablemente sea ideal si alguna vez necesita ordenar una colección de un millón de enteros que se sabe que están entre 0 y 100, por ejemplo.

Para implementar un ordenamiento de conteo muy simple que funcione con enteros con y sin signo, uno necesita encontrar los elementos más pequeños y más grandes en la colección para ordenar; su diferencia indicará el tamaño de la matriz de recuentos para asignar. Luego, se realiza una segunda pasada a través de la colección para contar el número de ocurrencias de cada elemento. Finalmente, reescribimos el número requerido de cada número entero a la colección original.

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

Si bien solo es útil cuando se sabe que el rango de los enteros para ordenar es pequeño (generalmente no es más grande que el tamaño de la colección para ordenar), hacer que el ordenamiento sea más genérico lo haría más lento para sus mejores casos. Si no se sabe que el rango es pequeño, se puede utilizar otro algoritmo como una clasificación de radix , ska_sort o spreadsort .

Detalles omitidos :

• Podríamos haber pasado los límites del rango de valores aceptados por el algoritmo como parámetros para eliminar por completo el primer std::minmax_elementpaso a través de la colección. Esto hará que el algoritmo sea aún más rápido cuando se conozca un límite de rango útilmente pequeño por otros medios. (No tiene que ser exacto; pasar un constante de 0 a 100 sigue siendo mucho mejor que un pase adicional sobre un millón de elementos para descubrir que los límites verdaderos son de 1 a 95. Incluso 0 a 1000 valdría la pena; el los elementos adicionales se escriben una vez con cero y se leen una vez).

• Crecer countssobre la marcha es otra forma de evitar un primer pase por separado. Duplicar el countstamaño cada vez que tiene que crecer da tiempo O (1) amortizado por elemento ordenado (consulte el análisis de costos de inserción de la tabla hash para la prueba de que el crecimiento exponencial es la clave). Crecer al final para un nuevo maxes fácil con std::vector::resizeagregar nuevos elementos a cero. Se puede cambiar minsobre la marcha e insertar nuevos elementos a cero en el frente std::copy_backwarddespués de hacer crecer el vector. Luego std::filla cero los nuevos elementos.

• El countsbucle de incremento es un histograma. Si es probable que los datos sean muy repetitivos, y el número de contenedores es pequeño, puede valer la pena desenrollarlo en múltiples arreglos para reducir el cuello de botella de la dependencia de datos serializados de almacenar / recargar en el mismo contenedor. Esto significa más recuentos hasta cero al comienzo y más para repetir al final, pero debería valer la pena en la mayoría de las CPU para nuestro ejemplo de millones de números de 0 a 100, especialmente si la entrada ya podría estar (parcialmente) ordenada y tener carreras largas del mismo número.

• En el algoritmo anterior, usamos una min == maxverificación para regresar temprano cuando cada elemento tiene el mismo valor (en cuyo caso la colección está ordenada). En realidad, es posible verificar completamente si la colección ya está ordenada mientras se encuentran los valores extremos de una colección sin perder tiempo adicional (si el primer paso todavía tiene un cuello de botella en la memoria con el trabajo adicional de actualizar min y max). Sin embargo, dicho algoritmo no existe en la biblioteca estándar y escribir uno sería más tedioso que escribir el resto del conteo en sí. Se deja como ejercicio para el lector.

• Dado que el algoritmo solo funciona con valores enteros, se podrían usar aserciones estáticas para evitar que los usuarios cometan errores de tipo obvio. En algunos contextos, se std::enable_if_tpodría preferir un fallo de sustitución con .

• Si bien el C ++ moderno es genial, el C ++ futuro podría ser aún más genial: los enlaces estructurados y algunas partes del Ranges TS harían que el algoritmo sea aún más limpio.