c++ - metodos - ordenamiento por intercambio

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

Question

El algoritmo std::sort (y sus primos std::partial_sort y std::nth_element ) de la biblioteca estándar de C ++ es, en la mayoría de las implementaciones, una amalgama complicada e híbrida de algoritmos de clasificación más elementales , como la clasificación por selección, la clasificación por inserción, la clasificación rápida , fusionar ordenar, o ordenar en montón.

Hay muchas preguntas aquí y en sitios hermanos como https://codereview.stackexchange.com/ relacionado 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, uso de 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 arriba utilizando C ++ moderno?

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

Notas :

• Para obtener referencias adicionales 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 en bruto es un ciclo más largo que la composición de dos funciones con un operador. Entonces f(g(x)); o f(x); g(x); f(x); g(x); o f(x) + g(x); no son bucles sin procesar, y tampoco lo son los bucles en selection_sort y insertion_sort continuación.
• Sigo la terminología de Scott Meyers para indicar el C ++ 1y actual como C ++ 14, y para indicar C ++ 98 y C ++ 03 como C ++ 98, así que no me llames por eso.
• Como se sugiere en los comentarios de @Mehrdad, proporciono cuatro implementaciones como 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. Donde sea relevante, denuncio las diferencias sintácticas y de biblioteca en las que difieren las diferentes versiones lingüísticas.

Answer 1

Bloques de construcción algorítmicos

Comenzamos por ensamblar 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 std::begin() / std::end() no miembro, así como con std::next() solo están disponibles a partir de C ++ 11 y posteriores. Para C ++ 98, uno necesita escribir estos mismos. Hay sustitutos de Boost.Range en boost::begin() / boost::end() , y de Boost.Utility en boost::next() .
• el algoritmo std::is_sorted solo está disponible para C ++ 11 y posteriores. Para C ++ 98, esto se puede implementar en términos de std::adjacent_find y un objeto de función escrito a mano. Boost.Algorithm también proporciona un boost::algorithm::is_sorted como sustituto.
• el algoritmo std::is_heap solo está disponible para C ++ 11 y posteriores.

Golosinas sintácticas

C ++ 14 proporciona comparadores transparentes de la forma std::less<> que actúan de forma polimórfica en 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 sobrecarga única para los algoritmos de clasificació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, uno 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 utilizar la sintaxis de typename xxx<yyy>::type verboso 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 amabilidad sintáctica es que C ++ 14 facilita el ajuste de comparadores definidos por el usuario a través de lambdas polimórficas (con parámetros auto que se deducen como argumentos de la 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 al tipo std::not1 de sintaxis std::bind1st / std::bind2nd / std::not1 .
• Boost.Bind mejora esto con boost::bind y la sintaxis de marcador de posición _1 / _2 .
• C ++ 11 y posteriores 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 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 de Herb Sutter "Almost Always Auto" y de Scott Meyers "Preferir auto a declaraciones de tipo específico" , por la cual la brevedad es insuperable, aunque a veces se disputed su claridad.
• "Distinguish () y {} Scott Meyers al crear objetos" y elige consistentemente la inicialización con refuerzo {} lugar de la antigua inicialización entre paréntesis () (para evitar todos los problemas más desconcertantes en el código genérico).
• Scott Meyers "Prefiere 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, para permitir la verificación invariante del bucle para sub-rangos ya ordenados. En el código de producción, el uso de while (first != last) y a ++first algún lugar dentro del bucle podría ser ligeramente mejor.

Selección 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 siempre O(N²) . Sin embargo, la selección por selección tiene la propiedad de minimizar el número de swaps . En aplicaciones donde el costo de intercambiar elementos es alto, la selección puede muy bien ser el algoritmo de elección.

Para implementarlo usando la biblioteca estándar, use repetidamente std::min_element para encontrar el elemento mínimo restante, e iter_swap para intercambiarlo 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 bucle invariante. Los requisitos mínimos son los iteradores hacia adelante , 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 los iteradores directos / bidireccionales: if (first == last || std::next(first) == last) return; ).
• para los iteradores bidireccionales , la prueba anterior se puede combinar con un bucle en el intervalo [first, std::prev(last)) , porque se garantiza que el último elemento es 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 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 adaptables ) o cuando el tamaño del problema es pequeño (porque tiene gastos indirectos bajos). Por estas razones, y debido a que también es estable , la clasificación por inserción se utiliza a menudo como el caso base recursivo (cuando el tamaño del problema es pequeño) para los algoritmos de clasificación de división y conquista de mayor sobrecarga, como la clasificación por fusión o la clasificación rápida.

Para implementar insertion_sort con la biblioteca estándar, use repetidamente std::upper_bound para encontrar la ubicación a la que debe ir el elemento actual, y use 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 bucle invariante. La ordenación por inserción también funciona con iteradores hacia adelante.

Detalles omitidos :

• la clasificación de inserción se puede optimizar con una prueba temprana if (std::distance(first, last) <= 1) return; (o para los iteradores hacia adelante / bidireccionales: if (first == last || std::next(first) == last) return; ) y un bucle durante el intervalo [std::next(first), last) , porque El primer elemento está 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 la Biblioteca estándar.

Cuatro ejemplos en vivo ( C++14 , C++11 , C ++ 98 y Boost , C++98 ) para el fragmento a continuación:

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 comparaciones de O(N²) , pero esto mejora a comparaciones de O(N) para entradas casi ordenadas. La búsqueda binaria siempre usa comparaciones O(N log N) .
• Para rangos de entrada pequeños, la mejor ubicación de memoria (caché, búsqueda 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 O(N log N) complejidad esperada, pero con O(N²) complejidad del peor caso que puede activarse con datos de entrada seleccionados adversamente. 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, la clasificación rápida es un poco más complicada de implementar utilizando la Biblioteca estándar que los otros algoritmos de clasificación clásicos. El siguiente enfoque usa 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) ) a la partición de tres vías la entrada rango en segmentos de elementos que son más pequeños, iguales y más grandes que el pivote seleccionado, respectivamente. Finalmente, los dos segmentos exteriores con elementos más pequeños y más grandes que el pivote se clasifican de forma recursiva:

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 de manera correcta y eficiente, ya que cada uno de los pasos anteriores debe comprobarse y optimizarse cuidadosamente para el código de nivel de producción. En particular, para la complejidad de O(N log N) , el pivote debe resultar en una partición equilibrada de los datos de entrada, lo que no se puede garantizar en general para un pivote O(1) , pero 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 complejidad O(N^2) para las entradas 1, 2, 3, ..., N/2, ... 3, 2, 1 del " tubo de órgano " ( porque el medio es siempre más grande que todos los demás elementos).
• median-of-3 selección de pivote de la median-of-3 partir de elementos elegidos al azar de las guardas de rango de entrada contra entradas casi ordenadas para las cuales la complejidad se deterioraría a O(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 a std::partition no es el algoritmo O(N) más eficiente para lograr este resultado.
• para los iteradores de acceso aleatorio , se puede lograr una complejidad O(N log N) garantizada mediante la 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 costoso que el de la complejidad O(1) de un pivote de mediana de 3 seguido de un O(N) llamada a std::partition (que es un paso directo simple y fácil de almacenar en caché sobre los datos).

Fusionar orden

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

Es fácil de implementar utilizando algoritmos estándar: use algunas utilidades de iterador para ubicar la mitad 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));
}

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

Tipo de pila

La ordenación de pila es simple de implementar, realiza una ordenación en el lugar O(N log N) , pero no es estable.

El primer bucle, O(N) "heapify" fase, pone la matriz en orden de pila. El segundo bucle, la fase de "clasificación" de O(N log 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 "engañoso" usar std::make_heap y std::sort_heap , puedes ir un nivel más profundo y escribir esas funciones 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 tanto push_heap como pop_heap como complejidad O(log N) . Sin embargo, make_heap cuenta que el bucle externo sobre el rango [first, last) da como resultado una complejidad O(N log N) para make_heap , mientras que std::make_heap solo tiene una complejidad O(N) . Para la complejidad general de O(N log N) de heap_sort no importa.

Detalles omitidos : O(N) implementación de make_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 (que no pretenden ser exhaustivas o rigurosas). Solo tenga en cuenta que las enormes diferencias en el LOC: C ++ 11 / C ++ 14 necesitan alrededor de 130 LOC, C ++ 98 y Boost 190 (+ 50%) y C ++ 98 más de 270 (+ 100%).

Answer 2

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

Contando orden

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

Para implementar una ordenación de conteo muy simple que funciona 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 dirá el tamaño de la matriz de conteos a 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, volvemos a escribir el número requerido de cada entero en 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 a ordenar es pequeño (generalmente no más grande que el tamaño de la colección a ordenar), hacer que la clasificación sea más genérica lo haría más lento para sus mejores casos. Si no se sabe que el rango sea pequeño, en su lugar se puede usar otro algoritmo como una clasificación de radix , ska_sort o spreadsort .

Detalles omitidos :

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

• El counts creciente sobre la marcha es otra forma de evitar una primera pasada separada. Duplicar el tamaño de los counts cada vez que tiene que crecer proporciona un tiempo amortizado O (1) por elemento ordenado (consulte el análisis de costos de inserción de la tabla hash para ver la prueba de que la clave es el crecimiento exponencial). Crecer al final para un nuevo max es fácil con std::vector::resize para agregar nuevos elementos puestos a cero. Cambiar min al vuelo e insertar nuevos elementos std::copy_backward cero en la parte delantera se puede hacer con std::copy_backward después de hacer crecer el vector. Entonces std::fill a cero los nuevos elementos.

• El bucle de incremento de counts es un histograma. Si es probable que los datos sean altamente repetitivos, y el número de contenedores sea pequeño, puede valer la pena desenrollarlos en múltiples arreglos para reducir el cuello de botella de la dependencia de datos de serialización de almacenamiento / recarga en el mismo contenedor. Esto significa que más cuentas a cero al comienzo, y más para hacer un bucle al final, pero debería valer la pena en la mayoría de las CPU para nuestro ejemplo de millones de 0 a 100 números, especialmente si la entrada ya puede estar ordenada (parcialmente) y tienen carreras largas del mismo número.

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

• Dado que el algoritmo solo funciona con valores enteros, se pueden usar aserciones estáticas para evitar que los usuarios cometan errores de tipo obvios. En algunos contextos, podría preferirse una falla de sustitución con std::enable_if_t .

• Si bien el C ++ moderno es genial, el C ++ futuro podría ser incluso más frío: los enlaces estructurados y algunas partes de los Rangos TS harán que el algoritmo sea aún más claro.