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 non-member
std::begin()/ std::end()así como with std::next()solo están disponibles a partir de C ++ 11 y posteriores. Para C ++ 98, es necesario 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 posteriores. Para C ++ 98, esto se puede implementar en términos de std::adjacent_findun objeto de función escrito a mano. Boost.Algorithm también proporciona boost::algorithm::is_sortedun sustituto.
- el
std::is_heapalgoritmo solo está disponible para C ++ 11 y posteriores.
Objetos sintácticos
C ++ 14 proporciona ¿Qué son los 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 plantilla predeterminados para plantillas de funciones C ++ 11 para crear una sola sobrecarga para ordenar algoritmos 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 Typedef de plantilla de C ++ reutilizable 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, es necesario 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 sutileza sintáctica es que C ++ 14 facilita envolver 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 la sintaxis
boost::bindy _1/ _2placeholder.
- C ++ 11 y posteriores también lo tienen
std::find_if_not, mientras que C ++ 98 necesita std::find_ifcon un std::not1objeto de función alrededor.
Estilo C ++
Todavía no existe un estilo C ++ 14 generalmente aceptable. Para bien o para mal, sigo de cerca el borrador Effective Modern C ++ de Scott Meyers y el renovado GotW de Herb Sutter . Utilizo las siguientes recomendaciones de estilo:
- La recomendación "Almost Always Auto" de Herb Sutter y "Preferir auto a declaraciones de tipo específico " de Scott Meyers , cuya brevedad es insuperable, aunque su claridad a veces se discute .
- "Distinguir
()y {}al crear objetos" de Scott Meyers y elegir constantemente la inicialización {}entre paréntesis ()en lugar de la inicialización entre paréntesis (para evitar todos los problemas de análisis más molestos en el código genérico).
- "Preferir declaraciones de alias a typedefs" de Scott Meyers . Para las plantillas, esto es imprescindible de todos modos, y usarlo en todas partes en lugar de
typedefahorra tiempo y agrega consistencia.
- Utilizo un
for (auto it = first; it != last; ++it)patrón en algunos lugares, para permitir la verificación invariante de bucle para subrangos ya ordenados. En el código de producción, el uso de while (first != last)y en ++firstalgún lugar dentro del ciclo podría ser un poco mejor.
Orden de selección
La clasificación 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, el ordenamiento por selección tiene la propiedad de minimizar el número de intercambios . En aplicaciones donde el costo de intercambiar artículos es alto, la ordenación por selección 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_swappara 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_sorttiene el rango ya procesado [first, it)ordenado como su invariante de bucle. Los requisitos mínimos son los iteradores de avance , 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 hacia adelante / bidireccionales :) if (first == last || std::next(first) == last) return;.
- para los 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.
Tipo de inserción
Aunque es uno de los algoritmos de clasificación elementales con el O(N²)peor de los casos, la clasificación por inserción es el algoritmo de elección, ya sea cuando los datos están casi ordenados (porque son adaptables ) 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 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 superiores, como la ordenación combinada o la ordenación rápida.
Para implementar insertion_sortcon la Biblioteca estándar, use repetidamente std::upper_boundpara encontrar la ubicación donde el elemento actual debe ir, 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 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 se garantiza que el primer elemento 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
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 a 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 clasificación rápida es robusta y tiene la O(N log N)complejidad esperada, pero con la O(N²)complejidad del peor de los casos que se puede activar con datos de entrada elegidos de manera adversa. Cuando no se necesita una clasificación estable, la clasificación rápida es una excelente clasificación de uso general.
Incluso para las versiones más simples, la ordenación rápida es un poco más complicada de implementar utilizando la Biblioteca estándar que los otros algoritmos de ordenación clásicos. El siguiente enfoque usa algunas utilidades de iterador para ubicar el elemento medio del rango de entrada [first, last)como pivote, luego usa dos llamadas a std::partition(que son O(N)) para dividir en tres direcciones el rango de entrada en segmentos de elementos que son más pequeños que, iguales a, y mayor 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 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 ordenación rápida es bastante complicada de hacer correcta y eficiente, ya que cada uno de los pasos anteriores debe ser revisado y optimizado cuidadosamente para el código de nivel de producción. En particular, por O(N log N)complejidad, el pivote tiene que resultar en 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 del " tubo de órgano " 1, 2, 3, ..., N/2, ... 3, 2, 1(porque el medio siempre es más grande que todos los demás elementos).
- ¿Número de comparaciones realizadas en la mediana de 3 funciones? selección de pivote¿Número de comparaciones realizadas en la mediana de 3 funciones? partir de¿Cómo obtener un elemento aleatorio de un contenedor C ++? del rango de entrada protege contra entradas casi clasificadas para las cuales la complejidad se deterioraría de otra manera
O(N^2).
- La partición de 3 vías (separar elementos más pequeños, iguales y más grandes que el pivote) como se muestra en las dos llamadas a
std::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 el uso de la selección de pivote medio 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
O(N)complejidad de std::nth_elementpuede ser más costoso que el de la O(1)complejidad de un pivote mediano de 3 seguido de una O(N)llamada a std::partition(que es un pase directo sencillo compatible con caché los datos).
Combinar ordenación
Si el uso de O(N)espacio adicional no es un problema, la ordenación por combinación es una excelente opción: es el único algoritmo de ordenación estable O(N log N) .
Es fácil 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 ordenados recursivamente con 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 std::inplace_merge. Tenga en cuenta que al ordenar listas vinculadas, la ordenación por combinación solo requiere O(log N)espacio adicional (para recursividad). El último algoritmo se implementa std::list<T>::sorten la biblioteca estándar.
Tipo de pila
La ordenación de montón es simple de implementar, realiza unaO(N log N)ordenación en el lugar, pero no es estable.
El primer ciclo, la O(N)fase "heapify", coloca la matriz en orden de pila. El segundo ciclo, la O(N log Nfase de "clasificación", extrae repetidamente el máximo y restaura el orden del montón. 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 considere que usar std::make_heapy es "trampa" std::sort_heap, puede ir un nivel más profundo y escribir esas funciones usted 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 tanto push_heapy pop_heapcomo la 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. Porque la O(N log N)complejidad general heap_sortno 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 ni riguroso). Solo tenga en cuenta las enormes 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%).
![Ponle una tapa. En realidad, ponle una tapa a todo. Consigue 12 tapas de cocina elásticas de silicona por $14. [Exclusivo]](https://ihow.pro/assets/images/640-400/b6pvitijogjkfzk9f2f0.jpg)
